Computational Geometry
Related: Approximate Convex Decomposition   Skeleton Extraction   Hierarchical Aggregation  

Current Contributors: Nancy Amato
Complex geometric objects are often umanageable and affects the efficiency of the algorithm using them. Our group investigates various shape approximation techniques and their application to create an alternate simplified representation of any geometric object.

Benefits of Shape Approximations:

  • Improvement in computational efficiency for future applications (eg., collison detection, animation).
  • Alias representation of object for applications like object matching, object deformation.

Approximate Convex Decomposition (ACD)

Partitioning complex models into ''approximately convex'' regions that allow certain operations to be computed more efficiently.

Skeleton Extraction

Extracting a simple structure that captures spatial properties of geometric objects

Hierarchical Aggregation

Grouping objects in a geometric scene into approximated ''super-objects'' for faster future processing

Related Publications

Planning Motions for Shape-Memory Alloy Sheets, Mukulika Ghosh, Daniel Tomkins, Jory Denny, Sam Rodriguez, Marco Morales Aguirre, Nancy M. Amato, Origami, Vol: 6, Issue: 6, pp. 501-511, Dec 2015. DOI: 10.1090/MBK/095.2/13
Keywords: Computational Geometry, Motion Planning
Links : [Published]


title={Planning motions for shape-memory alloy sheets},
author={Mukulika Ghosh and D. Tomkins and J. Denny and S. Rodr{\'i}guez and M. Morales and N. Amato},


Shape Memory Alloys (SMAs) are smart materials that can remember predefined shapes. A deformed SMA can transition to a trained shape by applying temperature changes to portions of the material. This reconfigurable property allows SMAs to be used in aeronautics, medicine, and other fields where dynamic re-engineering or actuation of components is required. In this work, we plan the motion of an SMA robot modeled as inflexible regions connected by flexible joints. In this work, we adapt an existing state-of-the-art motion planning algorithm to model the folding of an SMA robot from an unfolded flat state to a folded shape under feasibility constraints such as collision free motion and gravitational stability. Our results validate our model and algorithm by folding interesting 3D shapes using gravitationally stable motions, show flexibility in modeling various planning problems and significantly improved motions in comparable time to not using stability constraints.

Simultaneous Shape Decomposition and Skeletonization, Jyh-Ming Lien, John Keyser , Nancy M. Amato, In. Proc. of the 2006 ACM symposium on Solid and physical modeling, Cardiff, Wales, United Kingdom, Jun 2006. DOI: 10.1145/1128888.1128919
Keywords: Computational Geometry, Convex Decomposition
Links : [Published]


author = {Lien, Jyh-Ming and Keyser, John and Amato, Nancy M.},
title = {Simultaneous Shape Decomposition and Skeletonization},
year = {2006},
isbn = {1595933581},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {},
doi = {10.1145/1128888.1128919},
booktitle = {Proceedings of the 2006 ACM Symposium on Solid and Physical Modeling},
pages = {219–228},
numpages = {10},
keywords = {skeletonization, convex decomposition, multi-resolution skeleton},
location = {Cardiff, Wales, United Kingdom},
series = {SPM '06}


Shape decomposition and skeletonization share many common properties and applications. However, they are generally treated as independent computations. In this paper, we propose an iterative approach that simultaneously generates a hierarchical shape decomposition and a corresponding set of multi-resolution skeletons. In our method, a skeleton of a model is extracted from the components of its decomposition --- that is, both processes and the qualities of their results are interdependent. In particular, if the quality of the extracted skeleton does not meet some user specified criteria, then the model is decomposed into finer components and a new skeleton is extracted from these components. The process of simultaneous shape decomposition and skeletonization iterates until the quality of the skeleton becomes satisfactory. We provide evidence that the proposed framework is efficient and robust under perturbation and. deformation. We also demonstrate that our results can readily be used in problems including skeletal deformations and virtual reality navigation.