Convex Decomposition of Polyhedra and Robustness
Authors:
- Chanderjit L. BajajCBChanderjit L. Bajaj
- Tamal K. DeyTDTamal K. Dey
- 1 April 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 21 (2) , 339-364
Abstract
This paper presents a simple algorithm to compute a convex decomposition of a nonconvex polyhedron of arbitrary genus (handles) and shells (internal voids). For such a polyhedron S with n edges and rnotches (features causing nonconvexity in polyhedra), the algorithm produces a worst-case optimal $O(r^2 )$ number of convex polyhedra $S_i $, with $U_{i = 1}^k S_i = S$, in $O(nr^2 + r^{7/2} )$ time and $O(nr + r^{5/2} )$ space. Recently, Chazelle and Palios have given a fast $O((n + r^2 )\log r$) time and $O(n + r^2 )$ space algorithm to tetrahedralize a nonconvex polyhedron. Their algorithm, however, works for a simple polyhedron of genus zero and with no shells (internal voids). The algorithm, presented here, is based on the simple cut and split paradigm of Chazelle. With the help of zone theorems on arrangements, it is shown that this cut and split method is quite efficient. The algorithm is extended to work for a certain class of nonmanifold polyhedra. Also presented is an algorithm for the same problem that uses clever heuristics to overcome the numerical inaccuracies under finite precision arithmetic.
Keywords
This publication has 20 references indexed in Scilit:
- Triangulating a nonconvex polytopeDiscrete & Computational Geometry, 1990
- Polygon nesting and robustnessInformation Processing Letters, 1990
- Stable maintenance of point set triangulations in two dimensions1989
- Verifiable implementations of geometric algorithms using finite precision arithmeticArtificial Intelligence, 1988
- Arrangements of curves in the plane — topology, combinatorics, and algorithmsLecture Notes in Computer Science, 1988
- Algorithms in Combinatorial Geometry1987
- Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal AlgorithmSIAM Journal on Computing, 1984
- Some NP-hard polygon decomposition problemsIEEE Transactions on Information Theory, 1983
- The power of non-rectilinear holes1982
- On a problem of K. ZarankiewiczColloquium Mathematicum, 1954