Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
From MaRDI portal
Publication:3334982
DOI10.1137/0213031zbMATH Open0545.68031OpenAlexW2045155153MaRDI QIDQ3334982FDOQ3334982
Authors: Bernard Chazelle 
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
Recommendations
computational geometrydata structuresconvex decompositionsquadratic lower boundpartitions of polyhedra
Analysis of algorithms and problem complexity (68Q25) Polytopes and polyhedra (52Bxx) Polyhedra and polytopes; regular figures, division of spaces (51M20)
Cited In (49)
- Improved boundary constrained tetrahedral mesh generation by shell transformation
- A two-level method for mimetic finite difference discretizations of elliptic problems
- Computing optimal diameter-bounded polygon partitions
- Optimal complexity reduction of polyhedral piecewise affine systems
- Triangulation of simple arbitrarily shaped polyhedra by cutting off one vertex at a time
- Polygon nesting and robustness
- Parallel collision detection between moving robots for practical motion planning
- Using \(OxSim\) for path planning
- Decomposing the boundary of a nonconvex polyhedron
- Locking-free compressible quadrilateral finite elements: Poisson's ratio-dependent vector interpolants
- Delaunay partitions in \(\mathbb R^n\) applied to non-convex programs and vertex/facet enumeration problems
- Convex Invariant Refinement by Control Node Splitting: a Heuristic Approach
- Simplicial mesh of an arbitrary polyhedron.
- A Simple Algorithm to Triangulate a Special Class of 3d Non-convex Polyhedra Without Steiner Points
- Minimum convex partitions of multidimensional polyhedrons
- A singly exponential stratification scheme for real semi-algebraic varieties and its applications
- Vertical decompositions for triangles in 3-space
- Computational Science and Its Applications – ICCSA 2004
- Combinatorics of beacon-based routing in three dimensions
- Adaptive tetrahedral mesh generation by constrained Delaunay refinement
- Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming (CG Challenge)
- 3D boundary recovery by constrained Delaunay tetrahedralization
- Local polyhedra and geometric graphs
- Erased arrangements of linear and convex decompositions of polyhedra
- On Decomposition of Embedded Prismatoids in $$\mathbb {R}^3$$ Without Additional Points
- On the complexity of approximating and illuminating three-dimensional convex polyhedra
- Optimal tetrahedralization of the 3D-region ``between a convex polyhedron and a convex polygon
- Efficiently hex-meshing things with topology
- TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator
- Strategies for polyhedral surface decomposition: an experimental study.
- Searching polyhedra by rotating half-planes
- Decompositions and boundary coverings of non-convex fat polyhedra
- Free-Form Surface Partition in 3-D
- On \(d\)-convex partitions of polygonal regions
- Many-face complexity in incremental convex arrangements
- Exact Minkowksi sums of polyhedra and exact and efficient decomposition of polyhedra into convex pieces
- Graph problems arising from parameter identification of discrete dynamical systems
- Triangulating a nonconvex polytope
- The upper envelope of piecewise linear functions: Algorithms and applications
- Convex polygons made from few lines and convex decompositions of polyhedra
- Stability of the 8-tetrahedra shortest-interior-edge partitioning method
- A decision procedure for optimal polyhedron partitioning
- Bounds on the size of tetrahedralizations
- Minimizing visible edges in polyhedra
- Geometrical discretisations for unfitted finite elements on explicit boundary representations
- A fixed parameter algorithm for optimal convex partitions
- Removing depth-order cycles among triangles: an algorithm generating triangular fragments
- Decomposing the boundary of a nonconvex polyhedron
- Decomposing the complement of the union of cubes and boxes in three dimensions
This page was built for publication: Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3334982)
