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

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