Approximate convex decomposition of polygons

Jyh Ming Lien, Nancy M. Amato

Research output: Contribution to conferencePaper

Abstract

We propose a strategy to decompose a polygon, containing zero or more holes, into "approximately convex" pieces. For many applications, the approximately convex components of this decomposition provide similar benefits as convex components, while the resulting decomposition is significantly smaller and can be computed more efficiently. Moreover, our approximate convex decomposition (ACD) provides a mechanism to focus on key structural features and ignore less significant artifacts such as wrinkles and surface texture; a user specified tolerance determines allowable concavity. We propose a simple algorithm that computes an ACD of a polygon by iteratively removing (resolving) the most significant non-convex feature (notch). As a by product, it produces an elegant hierarchical representation that provides a series of 'increasingly convex' decompositions. Our algorithm computes an ACD of a simple polygon with n vertices and r notches in O(nr) time. In contrast, exact convex decomposition is NP-hard or, if the polygon has no holes, takes O(nr2) time.

Original languageEnglish (US)
Pages17-26
Number of pages10
DOIs
StatePublished - 2004
Externally publishedYes
EventProceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States
Duration: Jun 9 2004Jun 11 2004

Other

OtherProceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
CountryUnited States
CityBrooklyn, NY
Period6/9/046/11/04

Keywords

  • Convex decomposition
  • Hierarchical
  • Polygon

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Approximate convex decomposition of polygons'. Together they form a unique fingerprint.

  • Cite this

    Lien, J. M., & Amato, N. M. (2004). Approximate convex decomposition of polygons. 17-26. Paper presented at Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04), Brooklyn, NY, United States. https://doi.org/10.1145/997817.997823