Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
From MaRDI portal
Publication:3334982
DOI10.1137/0213031zbMath0545.68031OpenAlexW2045155153MaRDI 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 structurescomputational geometryconvex decompositionsquadratic lower boundpartitions of polyhedra
Analysis of algorithms and problem complexity (68Q25) Polyhedra and polytopes; regular figures, division of spaces (51M20) Polytopes and polyhedra (52Bxx)
Related Items
Simplicial mesh of an arbitrary polyhedron. ⋮ Many-face complexity in incremental convex arrangements ⋮ Exact Minkowksi sums of polyhedra and exact and efficient decomposition of polyhedra into convex pieces ⋮ Geometrical discretisations for unfitted finite elements on explicit boundary representations ⋮ Convex polygons made from few lines and convex decompositions of polyhedra ⋮ SEARCHING POLYHEDRA BY ROTATING HALF-PLANES ⋮ Bounds on the size of tetrahedralizations ⋮ Vertical decompositions for triangles in 3-space ⋮ Erased arrangements of linear and convex decompositions of polyhedra ⋮ Optimal tetrahedralization of the 3D-region ``between a convex polyhedron and a convex polygon ⋮ Minimizing visible edges in polyhedra ⋮ A Simple Algorithm to Triangulate a Special Class of 3d Non-convex Polyhedra Without Steiner Points ⋮ Graph problems arising from parameter identification of discrete dynamical systems ⋮ Locking-free compressible quadrilateral finite elements: Poisson's ratio-dependent vector interpolants ⋮ Triangulating a nonconvex polytope ⋮ Polygon nesting and robustness ⋮ The upper envelope of piecewise linear functions: Algorithms and applications ⋮ Efficiently hex-meshing things with topology ⋮ Removing depth-order cycles among triangles: an algorithm generating triangular fragments ⋮ A singly exponential stratification scheme for real semi-algebraic varieties and its applications ⋮ Combinatorics of beacon-based routing in three dimensions ⋮ Decomposing the boundary of a nonconvex polyhedron ⋮ Using OXSIM for path planning ⋮ Parallel collision detection between moving robots for practical motion planning ⋮ 3D boundary recovery by constrained Delaunay tetrahedralization ⋮ Optimal complexity reduction of polyhedral piecewise affine systems ⋮ Convex Invariant Refinement by Control Node Splitting: a Heuristic Approach ⋮ Strategies for polyhedral surface decomposition: an experimental study. ⋮ A two-level method for mimetic finite difference discretizations of elliptic problems ⋮ Decomposing the boundary of a nonconvex polyhedron ⋮ Adaptive tetrahedral mesh generation by constrained Delaunay refinement ⋮ Local polyhedra and geometric graphs ⋮ Improved boundary constrained tetrahedral mesh generation by shell transformation ⋮ Decompositions and boundary coverings of non-convex fat polyhedra ⋮ On Decomposition of Embedded Prismatoids in $$\mathbb {R}^3$$ Without Additional Points ⋮ TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator
