Abstract
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 language | English (US) |
---|---|
Pages (from-to) | 327-342 |
Number of pages | 16 |
Journal | Computational Geometry: Theory and Applications |
Volume | 7 |
Issue number | 5-6 |
DOIs | |
State | Published - Apr 1997 |
All Science Journal Classification (ASJC) codes
- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics
Keywords
- 3-SAT
- Convexity
- Flooding heuristics
- NP-completeness
- Surface decomposition