On the difficulty of triangulating three-dimensional nonconvex polyhedra

DOI10.1007/BF02187840zbMath0747.52009MaRDI QIDQ1182990

Jim Ruppert, Raimund Seidel

Publication date: 28 June 1992

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

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

zbMATH Keywords

partition of polyhedra3-dimensional nonconvex polyhedrontriangulation problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Computational aspects related to convexity (52B55) Polyhedra and polytopes; regular figures, division of spaces (51M20) Parallel algorithms in computer science (68W10) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (32)

Spatial polyhedra without diagonals ⋮ Simplicial mesh of an arbitrary polyhedron. ⋮ Redesign of a conformal boundary recovery algorithm for 3D Delaunay triangulation ⋮ Bounds on the size of tetrahedralizations ⋮ Regular triangulations and Steiner points ⋮ Fourth order accurate evaluation of integrals in potential theory on exterior 3D regions ⋮ Erased arrangements of linear and convex decompositions of polyhedra ⋮ Optimal tetrahedralization of the 3D-region ``between a convex polyhedron and a convex polygon ⋮ On triangulating three-dimensional polygons ⋮ Minimizing visible edges in polyhedra ⋮ A Simple Algorithm to Triangulate a Special Class of 3d Non-convex Polyhedra Without Steiner Points ⋮ Unnamed Item ⋮ Secondary polytope and secondary power diagram ⋮ A fast solver for the Stokes equations with distributed forces in complex geometries. ⋮ Starshaped sets ⋮ Overview and recent advances in natural neighbour Galerkin methods ⋮ Combinatorics of beacon-based routing in three dimensions ⋮ 3D boundary recovery by constrained Delaunay tetrahedralization ⋮ General-dimensional constrained Delaunay and constrained regular triangulations. I: Combinatorial properties ⋮ Strategies for polyhedral surface decomposition: an experimental study. ⋮ Adaptive tetrahedral mesh generation by constrained Delaunay refinement ⋮ 2D and 3D finite element meshing and remeshing ⋮ Local polyhedra and geometric graphs ⋮ An iterative interface reconstruction method for PLIC in general convex grids as part of a coupled level set volume of fluid solver ⋮ On nontriangulable polyhedra ⋮ Triangulation of simple arbitrarily shaped polyhedra by cutting off one vertex at a time ⋮ Improved boundary constrained tetrahedral mesh generation by shell transformation ⋮ Decompositions and boundary coverings of non-convex fat polyhedra ⋮ Practical unstructured splines: algorithms, multi-patch spline spaces, and some applications to numerical analysis ⋮ On Decomposition of Embedded Prismatoids in $$\mathbb {R}^3$$ Without Additional Points ⋮ TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator ⋮ Fast segment insertion and incremental construction of constrained Delaunay triangulations

Cites Work

• Triangulating a nonconvex polytope
• Triangulating point sets in space
• Tetrahedrizing point sets in three dimensions
• Finding simplicial subdivisions of polytopes
• Some NP-hard polygon decomposition problems
• Covering Polygons Is Hard
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the difficulty of triangulating three-dimensional nonconvex polyhedra