Approximate convex decomposition

Jyh Ming Lien, Nancy M. Amato

Research output: Contribution to conferencePaperpeer-review


A partitioning strategy that decomposes a given 2D or 3D model, in to 'approximately convex' pieces, is discussed. The strategy is based on the premise that for some models and applications, some of the non-convex features can be considered less significant, and allowed to remain in the final decomposition while removing others. The model is decomposed if its concavity exceeds the threshold τ. The result shows that if an application can sacrifice a little convexity, then algorithm can produce fewer components then the exact convex decomposition, in significantly less time.

Original languageEnglish (US)
Number of pages2
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


OtherProceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
Country/TerritoryUnited States
CityBrooklyn, NY


  • Concavity measure
  • Convex decomposition
  • Polygon
  • Polyhedron

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


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

Cite this