Nina Amenta wins Test of Time Award for paper on computer analysis of real-world objects

uc davis computer science nina amenta 3d graphics test time
A figure from the paper of laser range data (left), a reconstructed watertight model (middle) and the object's simplified medial axis (right). Graphic courtesy of Nina Amenta

Computer science professor Nina Amenta has received a test-of-time award from the peer-reviewed journal Computational Geometry: Theory and Applications for her 2001 paper, “The power crust, union of balls, and the medial axis transformation.” The award honors papers published in the journal that are at least 10 years old and have left a legacy on the field of computational geometry. She and her co-authors will receive certificates and a cash prize, split among them. 

“It is gratifying,” said Amenta, when asked what the recognition meant to her. “If I had to pick one paper from my early time as a researcher for someone to look at, it is this one. It is nice that my early work is remembered at all, and even better that it is remembered the way I would want it to be.” 

Computers cannot see like humans, so they interpret the 3D world from data points. The challenge is teaching a machine to quickly recognize these points—known as a data cloud—as the surface of a physical object. Though this 3D data point sampling is now a key part of self-driving cars and motion sensing, it was an emerging technology at the time.

In the paper, Amenta’s team proposed a solution by relating this problem to classical geometry using a method they dubbed, “the power crust.” The “crust” component referred to the output surface the computer forms based off input sensory data and the “power” refers to the “power diagram,” a name for a geometric shape they used in the study. The team was the first to link these two concepts and it provided a conceptual framework that researchers in computational geometry still use today. 

“It was an elegant idea,” said Amenta. “Easy to explain, easy to implement, and simple enough that you can prove something about what kind of sampling patterns it works for.  I think that is why people still study it.” 

The paper was written by Amenta, Sunghee Choi and Ravi Kolluri—two of her first Ph.D. students. Almost 20 years later, Choi is a professor at the Korea Advanced Institute of Science and Technology, Kolluri works at Alphabet’s X and Amenta has had a successful career at UC Davis modeling the real world in 3D on a computer. 

Learn more.