article

Triangulating a nonconvex polytope

Authors:

Bernard Chazelle,

Leonidas PaliosAuthors Info & Claims

Discrete & Computational Geometry, Volume 5, Issue 5

Pages 505 - 526

https://doi.org/10.1007/BF02187807

Published: 01 December 1990 Publication History

Abstract

This paper is concerned with the problem of partitioning a three-dimensional nonconvex polytope into a small number of elementary convex parts. The need for such decompositions arises in tool design, computer-aided manufacturing, finite-element methods, and robotics. Our main result is an algorithm for decomposing a nonconvex polytope of zero genus withn vertices andr reflex edges intoO(n +r2) tetrahedra. This bound is asymptotically tight in the worst case. The algorithm requiresO(n +r2) space and runs inO((n +r2) logr) time.

References

[1]

B. Aronov and M. Sharir, Triangles in Space, or Building and Analyzing Castles in the Air,Proc. 4th Ann. ACM Symp. Comput. Geom. (1988), 381---391.

[2]

C. L. Bajaj and T. K. Dey, Robust Decompositions of Polyhedra, Dept. Computer Science, Purdue University, 1989.

[3]

T. J. Baker, Three-Dimensional Mesh Generation by Triangulation of Arbitrary Point Sets, Dept. Mechanical Engineering, Princeton University, 1986.

[4]

B. S. Baker, E. Grosse, and C. S. Rafferty, Non-Obtuse Triangulation of Polygons,Discrete Comput. Geom.3 (1988), 147---168.

Digital Library

[5]

B. G. Baumgart, A Polyhedron Representation for Computer Vision,Proc. 1975 National Comput. Conf., saAFIPS Conference Proceedings, Vol. 44, AFIPS Press, Montvale, NJ, 1975, 589---596.

[6]

J. F. Canny, A new Algebraic Method for Motion Planning and Real Geometry,Proc. 28th Ann. IEEE Symp. on Found. Comput. Sci. (1987), 39---48.

[7]

B. Chazelle, Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm,SIAM J. Comput.13 (1984), 488---507.

Digital Library

[8]

B. Chazelle, Approximation and Decomposition of Shapes,Advances in Robotics, Vol. 1 (J. T. Schwartz and C. K. Yap, ed.), Erlbaum, Hillsdale, NJ, 1987, 145---185.

[9]

B. Chazelle, H. Edelsbrunner, L. J. Guibas, and M. Sharir, A Singly-Exponential Stratification Scheme for Real Semi-Algebraic Varieties and Its Applications,Proc. 16th ICALP, Lecture Notes in Computer Science, Vol. 372, Springer-Verlag, Berlin, 1989, 179---193.

[10]

B. Chazelle, L. J. Guibas, and D. T. Lee, The Power of Geometric Duality,BIT25 (1985), 76---90.

[11]

G. E. Collins, Quantifier Elimination for Real Closed Fields by Cylindric Algebraic Decomposition,Proc. 2nd Gl Conf. Automata Theory and Formal Languages, Lecture Notes in Computer Science, Vol 33, Springer-Verlag, Berlin, 1975, 134---183.

[12]

D. P. Dobkin and M. J. Laszlo, Primitives for the Manipulation of Three-Dimensional Subdivisions,Proc. 3rd Ann. ACM Symp. Comput. Geom. (1987), 86---99.

[13]

H. Edelsbrunner, L. J. Guibas, and J. Stolfi, Optimal Point Location in a Monotone Subdivision,SIAM J. Comput.15 (1986), 317---340.

Digital Library

[14]

H. Edelsbrunner, J. O'Rourke, and R. Seidel, Constructing Arrangements of Lines and Hyperplanes with Applications,SIAM J. Comput.15 (1986), 341---363.

Digital Library

[15]

H. Feng and T. Pavlidis, Decomposition of Polygons into Simpler Components: Feature Generation for Syntactic Pattern Recognition,IEEE Trans. Comput.24 (1975), 636---650.

Digital Library

[16]

D. A. Field, Implementing Watson's Algorithm in Three Dimensions,Proc. 2nd Ann. ACM Symp. Comput. Geom. (1986), 246---259.

[17]

L. J. Guibas and J. Stolfi, Primitives for the Manipulating of General Subdivisions and the Computation of Voronoi Diagrams,ACM Trans. Graphics4 (1985), 75---123.

[18]

D. G. Kirkpatrick Optimal Search in Planar Subdivisions,SIAM J. Comput.12 (1983), 28---35.

[19]

A. Lingas, The Power of Non-Rectilinear Holes,Proc. 9th Colloq. Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 140, Springer-Verlag, Berlin, 1982, 369---383.

[20]

K. Mehlhorn,Data Structures and Algorithms, Vol. 3, Springer-Verlag, Berlin, 1984.

[21]

D. E. Muller and F. P. Preparata, Finding the Intersection of Two Convex Polyhedra,Theoret. Comput. Sci.7 (1978), 217---236.

[22]

J. O'Rourke,Art Gallery Theorems and Algorithms, Oxford University Press, Oxford, 1987.

[23]

F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985.

Digital Library

[24]

D. Prill, On Approximations and Incidence in Cylindrical Algebraic Decompositions,SIAM J. Comput.15 (1986), 972---993.

[25]

J. Ruppert and R. Seidel, On the Difficulty of Tetrahedralizing 3-Dimensional Non-Convex Polyhedra,Proc. 5th Ann. ACM Symp Comput. Geom. (1989), 380---392.

[26]

B. Schachter, Decomposition of Polygons into Convex Sets,IEEE Trans. Comput.27 (1978), 1078---1082.

[27]

J. T. Schwartz and M. Sharir, On the "Piano Movers" Problem, II: General Techniques for Computing Topological Properties of Real Algebraic Manifolds,Adv. in Appl. Math.4 (1983), 298---351.

Digital Library

[28]

W. Smith, Studies in Computational Geometry Motivated by Mesh Generation, Ph.D. Thesis, Princeton University, 1988.

[29]

H. Whitney, Elementary Structure of Real Algebraic Varieties,Ann. of Math.66 (1957), 545---556.

Cited By

Alexa M(2020)Conforming weighted delaunay triangulationsACM Transactions on Graphics10.1145/3414685.341777639:6(1-16)Online publication date: 27-Nov-2020
https://dl.acm.org/doi/10.1145/3414685.3417776
Aurenhammer FWalzl G(2016)Straight Skeletons and Mitered Offsets of Nonconvex PolytopesDiscrete & Computational Geometry10.1007/s00454-016-9811-556:3(743-801)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s00454-016-9811-5
Si H(2015)TetGen, a Delaunay-Based Quality Tetrahedral Mesh GeneratorACM Transactions on Mathematical Software10.1145/262969741:2(1-36)Online publication date: 4-Feb-2015
https://dl.acm.org/doi/10.1145/2629697
Show More Cited By

Index Terms

Triangulating a nonconvex polytope

Index terms have been assigned to the content through auto-classification.

Recommendations

Lifting facets of the cut polytope

The cut polytope P"c(G) of a graph G is the convex hull of the incidence vectors of the edge sets of all cuts of G. We give a sufficient condition for an inequality defining a facet of P"c(G) to define a facet of the cut polytope of a graph containing G ...
On the cut polytope

The cut polytopePC(G) of a graphG=(V, E) is the convex hull of the incidence vectors of all edge sets of cuts ofG. We show some classes of facet-defining inequalities ofPC(G). We describe three methods with which new facet-defining inequalities ofPC(G) ...
An Upper Bound Theorem for Polytope Pairs

Assume P* is a simple, convex, d-polytope with ν facets, and F* is a simple, convex d'-polytope with ν' facets, where 0 ≤ d' ≤ d-1. If F* is in fact a face of P* we call P*, F* a polytope pair of type d, ν, d', ν'. Define Q* to be P* ∼ F*, the unbounded,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete & Computational Geometry

Discrete & Computational Geometry Volume 5, Issue 5

October 1990

101 pages

ISSN:0179-5376

Issue’s Table of Contents

Copyright © Copyright © 1990 Springer-Verlag New York Inc.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 December 1990

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alexa M(2020)Conforming weighted delaunay triangulationsACM Transactions on Graphics10.1145/3414685.341777639:6(1-16)Online publication date: 27-Nov-2020
https://dl.acm.org/doi/10.1145/3414685.3417776
Aurenhammer FWalzl G(2016)Straight Skeletons and Mitered Offsets of Nonconvex PolytopesDiscrete & Computational Geometry10.1007/s00454-016-9811-556:3(743-801)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s00454-016-9811-5
Si H(2015)TetGen, a Delaunay-Based Quality Tetrahedral Mesh GeneratorACM Transactions on Mathematical Software10.1145/262969741:2(1-36)Online publication date: 4-Feb-2015
https://dl.acm.org/doi/10.1145/2629697
Erickson J(2014)Efficiently Hex-Meshing Things with TopologyDiscrete & Computational Geometry10.1007/s00454-014-9624-352:3(427-449)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1007/s00454-014-9624-3
Erickson Jda Fonseca GLewiner TPeñaranda LChan TKlein R(2013)Efficiently hex-meshing things with topologyProceedings of the twenty-ninth annual symposium on Computational geometry10.1145/2462356.2462403(37-46)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1145/2462356.2462403
Lee D(2010)Computational geometry IAlgorithms and theory of computation handbook10.5555/1882723.1882724(1-1)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/1882723.1882724
Hu JHu XZhang WZhu SLiu ZHuang J(2009)Monotonic indices space method and its application in the capability indices effectiveness analysis of a notional antistealth information systemIEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans10.1109/TSMCA.2008.201079339:2(404-413)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1109/TSMCA.2008.2010793
Wan HHan XZhou ZRahardja SWu EThalmann DHuang Z(2008)Haptic rendering of complex objects via directional samplingProceedings of The 7th ACM SIGGRAPH International Conference on Virtual-Reality Continuum and Its Applications in Industry10.1145/1477862.1477889(1-7)Online publication date: 8-Dec-2008
https://dl.acm.org/doi/10.1145/1477862.1477889
Verbree ESi H(2008)Validation and Storage of Polyhedra through Constrained Delaunay TetrahedralizationProceedings of the 5th international conference on Geographic Information Science10.1007/978-3-540-87473-7_23(354-369)Online publication date: 23-Sep-2008
https://dl.acm.org/doi/10.1007/978-3-540-87473-7_23
Hwan Kim DDong Yun IUk Lee S(2006)Boundary-trimmed 3D triangular mesh segmentation based on iterative merging strategyPattern Recognition10.1016/j.patcog.2005.11.02239:5(827-838)Online publication date: 1-May-2006
https://dl.acm.org/doi/10.1016/j.patcog.2005.11.022
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents