Compatible tetrahedralizations

ABSTRACT

We give some special-case tetrahedralization algorithms. We first consider the problem of finding a tetrahedralization compatible with a fixed triangulation of the boundary of a polyhedron. We then adapt our solution to the related problem of compatibly tetrahedralizing the interior and exterior of a polyhedron. We also show how to tetrahedralize the region between nested convex polyhedra with O(n log n) tetrahedra and no Steiner points.

REFERENCES

• 1: A. Aggarwal , L. J. Guibas , J. Saxe , P. W. Shor, A linear-time algorithm for computing the Voronoi diagram of a convex polygon, Discrete & Computational Geometry, v.4 n.6, p.591-604, Sep. 1989 [doi>10.1007/BF02187749]
• 2: D. Avis and H. EiGindy. Triangulating point sets in space. Disc. and Comp. Geometry 2 (1987), 99-111.
• 3: M. Bern and D. Eppstein. Mesh generation and optimal triangulation. Xerox PARC Tech. Report CSL-92-1. Also in Computing in Euclidean Geometry, World Scientific, Singapore, 1992.
• 4: Bernard Chazelle, Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm, SIAM Journal on Computing, v.13 n.3, p.488-507, August 1984 [doi>10.1137/0213031]
• 5: Bernard Chazelle, An optimal algorithm for intersecting three-dimensional convex polyhedra, SIAM Journal on Computing, v.21 n.4, p.671-696, Aug. 1992 [doi>10.1137/0221041]
• 6: Bernard Chazelle , Herbert Edelsbrunner , Leonidas Guibas , Micha Sharir, Diameter, width, closest line pair, and parametric searching, Proceedings of the eighth annual symposium on Computational geometry, p.120-129, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142702]
• 7: Bernard Chazelle , Leonidas Palios, Triangulating a nonconvex polytope, Discrete & Computational Geometry, v.5 n.5, p.505-526, 1990 [doi>10.1007/BF02187807]
• 8: Cecil Jose A. Delfinado , Herbert Edelsbrunner, An incremental algorithm for Betti numbers of simplicial complexes, Proceedings of the ninth annual symposium on Computational geometry, p.232-239, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161140]
• 9: David P. Dobkin , David G. Kirkpatrick, Fast Detection of Polyhedral Intersections, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.154-165, July 12-16, 1982
• 10: B.R. Donald and D.R. Chang. On computing the homology type of a triangulation. Tech. Report TR-91-1183, Computer Science Dept., Cotnell University, 1991.
• 11: H. Edelsbrunner , F. P. Preparata , D. B. West, Tetrahedrizing point sets in three dimensions, Journal of Symbolic Computation, v.10 n.3-4, p.335-347, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80068-5]
• 12: D. Eppstein. Dynamic three-dimensional linear programming. ORSA J. Computing 4 (1992), 360-368.
• 13: J.E. Goodman and J. Pach. Cell decomposition of polytopes by bending. Israel j. of Math. 64 (1988), 129-138.
• 14: John Hershberger , Jack Snoeyink, Convex Polygons Made from Few Lines and Convex Decompositions of Polyhedra, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.376-387, July 08-10, 1992
• 15: D. Kirkpatrick. Optimal search in planar subdivisions. SIAM J. Computing 12 (1983), 28-35.
• 16: N.J. Lennes. Theorems on the simple finite polygon and polyhedron. Am. J. Math. 33 (1911), 37- 62.
• 17: Jim Ruppert , Raimund Seidel, On the difficulty of triangulating three-dimensional nonconvex polyhedra., Discrete & Computational Geometry, v.7 n.3, p.227-253, 1992 [doi>10.1007/BF02187840]
• 18: E. Schanhardt. ~lber die Zerlegung yon Dreieckspolyedern in Tetraeder. Math. Annalen 98 (1928), 309-312.
• 19: The VNR Concise Encyclopedia of Mathematics, Gellert et al., eds., Van Nostrand Reinhold, 1977, 262-265.
• 20: B. Von Hohenbalken. Finding simplicial subdivisions ofpolytopes. Math. Programming 21 (1981), 233-234.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory, Verification