Triangulating a nonconvex polytope

DOI10.1007/BF02187807zbMath0701.68038OpenAlexW4232767429MaRDI QIDQ914375

Leonidas Palios, Bernard Chazelle

Publication date: 1990

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131134

zbMATH Keywords

triangulation algorithmpolytope partitioning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)

Related Items (27)

Provably good mesh generation ⋮ Simplicial mesh of an arbitrary polyhedron. ⋮ Boundary-trimmed 3D triangular mesh segmentation based on iterative merging strategy ⋮ Exact Minkowksi sums of polyhedra and exact and efficient decomposition of polyhedra into convex pieces ⋮ Convex polygons made from few lines and convex decompositions of polyhedra ⋮ SEARCHING POLYHEDRA BY ROTATING HALF-PLANES ⋮ Straight skeletons and mitered offsets of nonconvex polytopes ⋮ Approximating the minimum triangulation of convex 3-polytopes with bounded degrees ⋮ Bounds on the size of tetrahedralizations ⋮ TOPOLOGY-PRESERVING WATERMARKING OF VECTOR GRAPHICS ⋮ Erased arrangements of linear and convex decompositions of polyhedra ⋮ Optimal tetrahedralization of the 3D-region ``between a convex polyhedron and a convex polygon ⋮ A Simple Algorithm to Triangulate a Special Class of 3d Non-convex Polyhedra Without Steiner Points ⋮ Efficiently hex-meshing things with topology ⋮ Overview and recent advances in natural neighbour Galerkin methods ⋮ A singly exponential stratification scheme for real semi-algebraic varieties and its applications ⋮ Tetrahedral meshes from planar cross-sections ⋮ On the difficulty of triangulating three-dimensional nonconvex polyhedra ⋮ Decomposing the boundary of a nonconvex polyhedron ⋮ 3D boundary recovery by constrained Delaunay tetrahedralization ⋮ Quasi-optimal upper bounds for simplex range searching and new zone theorems ⋮ Strategies for polyhedral surface decomposition: an experimental study. ⋮ Decomposing the boundary of a nonconvex polyhedron ⋮ An iterative interface reconstruction method for PLIC in general convex grids as part of a coupled level set volume of fluid solver ⋮ Dynamic motion planning in low obstacle density environments ⋮ A decomposition-based approach to layered manufacturing ⋮ TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• Elementary structure of real algebraic varieties
• The power of geometric duality
• Nonobtuse triangulation of polygons
• Finding the intersection of two convex polyhedra
• Triangles in space or building (and analyzing) castles in the air
• Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Optimal Point Location in a Monotone Subdivision
• Constructing Arrangements of Lines and Hyperplanes with Applications
• On Approximations and Incidence in Cylindrical Algebraic Decompositions
• Optimal Search in Planar Subdivisions
• Decomposition of Polygons into Simpler Components: Feature Generation for Syntactic Pattern Recognition
• Decomposition of Polygons into Convex Sets

This page was built for publication: Triangulating a nonconvex polytope