Approximate convex decomposition

Jyh Ming Lien, Nancy M. Amato

Research output: Contribution to conferencePaperpeer-review

Abstract

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)
Pages457-458
Number of pages2
StatePublished - Oct 4 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

  • Concavity measure
  • Convex decomposition
  • Polygon
  • Polyhedron

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

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

Cite this