Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
From MaRDI portal
Publication:3334982
DOI10.1137/0213031zbMath0545.68031MaRDI QIDQ3334982
Publication date: 1984
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0213031
data structures; computational geometry; convex decompositions; quadratic lower bound; partitions of polyhedra
68Q25: Analysis of algorithms and problem complexity
51M20: Polyhedra and polytopes; regular figures, division of spaces
52Bxx: Polytopes and polyhedra
Related Items
Decomposing the boundary of a nonconvex polyhedron, Exact Minkowksi sums of polyhedra and exact and efficient decomposition of polyhedra into convex pieces, Triangulating a nonconvex polytope, Polygon nesting and robustness, The upper envelope of piecewise linear functions: Algorithms and applications, Optimal complexity reduction of polyhedral piecewise affine systems, Decompositions and boundary coverings of non-convex fat polyhedra, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, Many-face complexity in incremental convex arrangements, Erased arrangements of linear and convex decompositions of polyhedra, Local polyhedra and geometric graphs, Simplicial mesh of an arbitrary polyhedron., Bounds on the size of tetrahedralizations, Vertical decompositions for triangles in 3-space, Optimal tetrahedralization of the 3D-region ``between a convex polyhedron and a convex polygon, Strategies for polyhedral surface decomposition: an experimental study., Using OXSIM for path planning, Parallel collision detection between moving robots for practical motion planning, Adaptive tetrahedral mesh generation by constrained Delaunay refinement
