Strategies for polyhedral surface decomposition: An experimental study

Bernard Chazelle, David Paul Dobkin, Nadia Shouraboura, Ayellet Tal

Research output: Contribution to journalArticlepeer-review

86 Scopus citations


This paper addresses the problem of decomposing a complex polyhedral surface into a small number of "convex" patches (i.e., boundary parts of convex polyhedra). The corresponding optimization problem is shown to be NP-complete and an experimental search for good heuristics is undertaken.

Original languageEnglish (US)
Pages (from-to)327-342
Number of pages16
JournalComputational Geometry: Theory and Applications
Issue number5-6
StatePublished - Apr 1997

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics


  • 3-SAT
  • Convexity
  • Flooding heuristics
  • NP-completeness
  • Surface decomposition


Dive into the research topics of 'Strategies for polyhedral surface decomposition: An experimental study'. Together they form a unique fingerprint.

Cite this