“Approximate Convex Decomposition of Polyhedra” by Lien and Amato

  • ©Jyh-Ming Lien and Nancy M. Amato

  • ©Jyh-Ming Lien and Nancy M. Amato



Entry Number: 002


    Approximate Convex Decomposition of Polyhedra



    Decomposition is a technique commonly used to break com- plex models into sub-models that are easier to handle. Convex decomposition, which partitions the model into convex components, is interesting because many algorithms perform more efficiently on convex objects than on non-convex objects. One issue with convex decompositions, however, is that they can be costly to construct and can result in representations with an unmanageable number of components. In many applications, feature details are not crucial and in fact considering them could obscure important structural information and add to the processing cost. In such cases, an approximate representation of the model that captures the key structural features would be preferable.


    1. Chazelle, B., Dobkin, D. P., Shouraboura, N., and Tal, A. 1995. Strategies for polyhedral surface decomposition: An experimental study. In Proc. 11th Annu. ACM Sympos. Comput. Geom., 297–305.
    2. Katz, S., and Tal, A. 2003. Hierarchical mesh decomposition using fuzzy clustering and cuts. ACM Trans. Graph. 22, 3, 954–961.
    3. Lien, J.-M., and Amato, N. M. 2003. Approximate convex decomposition. Tech. Rep. TR03-001, Parasol Lab, Dept. of Computer Science, Texas A&M University.
    4. Lien, J.-M., and Amato, N. M. 2004. Approximate convex decomposition of polygons. In Proc. 20th Annual ACM Symp. Computat. Geom. (SoCG), 17–26.


ACM Digital Library Publication:

Overview Page: