January 3, 2010 | Eli Freund - School of Engineering

Geometric Skeletons

That is the premise behind Dr. Horea Ilies' new grant from the National Science Foundation. An assistant professor of Mechanical Engineering, Dr. Ilies has proposed a new way to define classes and families of skeletons that characterize, describe and manipulate geometry.

By Kate Kurtin

horea photoNew theoretical results can shift even fundamental concepts. That is the premise behind Dr. Horea Ilies’ new grant from the National Science Foundation. An assistant professor of Mechanical Engineering, Dr. Ilies has proposed a new way to define classes and families of skeletons that characterize, describe and manipulate geometry.

These geometric skeletons play a role similar to that of human skeletons, in that they capture the main features of the shape that defines them. “If you see the skeleton of a mammal you can tell many things about the animal that it comes from even though you may not know the actual details of the body surface” Dr. Ilies explains.

Geometric skeletons are fundamental concepts in practically all geometrically intensive areas of science and engineering, such as automated finite element meshing, shape manipulation, recognition and comparison, dimensional reduction in design and analysis, robotic surgery, and a variety of path and motion planning in commercial and defense applications. More recently, skeletons have been used to explore the fundamental geometric problems of folding and unfolding that are the abstraction of some of the most important open problems in science today, such as protein folding, packing, and sheet metal bending. Dr. Ilies points out that shape skeletons are mathematically well understood, but difficult to compute. “What this grant is about is really proposing a new way to define and compute not just single, but also classes of skeletons. This new way of looking at the problem allows us to compute these skeletons in many more situations than was previously possible,” Dr. Ilies clarified.

horea photoThough widely used in engineering, computer graphics and computer vision, the underlying algorithms used to compute shape skeletons are still restricted to fairly simple and static shapes. By contrast, many practical applications, such as motion planning of unmanned autonomous vehicles, materialize in environments that are either not completely known, or must evolve in time as new information becomes available. This requires the ability to handle evolving environments in which obstacles can appear/disappear as well as merge/split with other obstacles or with the boundary of the environment itself. Mathematically, this means that the typology of the environment is changing drastically, “hampering our ability to “reason” in these environments” Dr. Ilies explained. “What our formulation allows us to do is to account for such evolutions in the environment while maintaining the ability to compute the skeletons” Dr. Ilies said. “Our approach remains valid for arbitrarily complex geometry, which is a big step forward,” Dr. Ilies explains.

At the conclusion of the three-year grant period, working with graduate students in his lab, including doctoral student Ata Eftekharian, Dr. Ilies intends to have created the foundations necessary for computations of both 2- and 3-dimensional shape skeletons. “Right now we are concentrating on 2-D shapes and beginning the work on 3-D,” Dr. Ilies explained. Success in computing skeletons of 3-D shapes will have enormous implications to industrial applications such as those identified above.