Incrementally Constructing and Updating Constrained Delaunay Tetrahedralizations with Finite Precision Coordinates

1. Boissonnat, J.-D., Devillers, O., Pion, S., Teillaud, M., Yvinec, M.: Triangulations in CGAL. Computational Geometry: Theory and Applications 22(1-3), 5–19 (2002)

   Article  MathSciNet  MATH  Google Scholar 

2. Bowyer, A.: Computing Dirichlet tessellations. The Computer Journal 24(2), 162–166 (1981)

   Article  MathSciNet  Google Scholar 

3. Cheng, S.-W., Dey, T.K., Edelsbrunner, H., Facello, M.A., Teng, S.-H.: Sliver exudation. Journal of the Association for Computing Machinery 47(5), 883–904 (2000)

   Article  MathSciNet  Google Scholar 

4. Paul Chew, L.: Building Voronoi diagrams for convex polygons in linear expected time. Technical Report PCS-TR90-147, Department of Mathematics and Computer Science, Dartmouth College (1990)

   Google Scholar 

5. Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry, II. Discrete & Computational Geometry 4(1), 387–421 (1989)

   Article  MathSciNet  MATH  Google Scholar 

6. Devillers, O., Pion, S., Teillaud, M.: Walking in a triangulation. In: Proceedings of the Seventeenth Annual Symposium on Computational Geometry, Medford, Massachusetts, pp. 106–114 (June 2001)

   Google Scholar 

7. Edelsbrunner, H., Mücke, E.P.: Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics 9(1), 66–104 (1990)

   Article  MATH  Google Scholar 

8. Fortune, S., Van Wyk, C.J.: Static analysis yields efficient exact integer arithmetic for computational geometry. ACM Transactions on Graphics 15(3), 223–248 (1996)

   Article  Google Scholar 

9. Guigue, P., Devillers, O.: Fast and robust triangle-triangle overlap test using orientation predicates. Journal of Graphics Tools 8(1), 25–32 (2003)

   Google Scholar 

10. Lee, D.-T., Lin, A.K.: Generalized Delaunay triangulations for planar graphs. Discrete & Computational Geometry 1, 201–217 (1986)

    Article  MathSciNet  MATH  Google Scholar 

11. Miller, G.L., Talmor, D., Teng, S.-H., Walkington, N.J., Wang, H.: Control volume meshes using sphere packing: Generation, refinement and coarsening. In: Proceedings of the 5th International Meshing Roundtable, Pittsburgh, Pennsylvania, pp. 47–61 (October 1996)

    Google Scholar 

12. Mücke, E.P.: Shapes and Implementations in Three-Dimensions Geometry. Ph.D. thesis, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois (1993)

    Google Scholar 

13. Seidel, R.: Voronoi diagrams in higher dimensions. Diplomarbeit, Institut für Informationsverarbeitung, Technische Universität Graz (1982)

    Google Scholar 

14. Shewchuk, J.R.: Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18(3), 305–363 (1997)

    Article  MathSciNet  MATH  Google Scholar 

15. Shewchuk, J.R.: A condition guaranteeing the existence of higher-dimensional constrained Delaunay triangulations. In: Proceedings of the Fourteenth Annual Symposium on Computational Geometry, pp. 76–85 (June 1998)

    Google Scholar 

16. Shewchuk, J.R.: Tetrahedral mesh generation by Delaunay refinement. In: Proceedings of the Fourteenth Annual Symposium on Computational Geometry, Minneapolis, Minnesota, pp. 86–95 (June 1998)

    Google Scholar 

17. Shewchuk, J.R.: Sweep algorithms for constructing higher-dimensional constrained Delaunay triangulations. In: Proceedings of the Sixteenth Annual Symposium on Computational Geometry, Hong Kong, pp. 350–359 (June 2000)

    Google Scholar 

18. Shewchuk, J.R.: Constrained Delaunay tetrahedralizations and provably good boundary recovery. In: Proceedings of the 11th International Meshing Roundtable, Ithaca, New York, pp. 193–204 (September 2002)

    Google Scholar 

19. Shewchuk, J.R.: Updating and constructing constrained Delaunay and constrained regular triangulations by flips. In: Proceedings of the Nineteenth Annual Symposium on Computational Geometry, pp. 181–190 (June 2003)

    Google Scholar 

20. Shewchuk, J.R.: General-dimensional constrained Delaunay triangulations and constrained regular triangulations I: Combinatorial properties. Discrete & Computational Geometry 39(1-3), 580–637 (2008)

    Article  MathSciNet  MATH  Google Scholar 

21. Si, H., Gärtner, K.: Meshing piecewise linear complexes by constrained Delaunay tetrahedralizations. In: Hanks, B.W. (ed.) Proceedings of the Fourteenth International Meshing Roundtable, pp. 147–163 (September 2005)

    Google Scholar 

22. Si, H., Gärtner, K.: 3D boundary recovery by constrained Delaunay tetrahedralization. International Journal for Numerical Methods in Engineering 85(11), 1341–1364 (2011)

    Article  MathSciNet  MATH  Google Scholar 

23. Watson, D.F.: Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. The Computer Journal 24(2), 167–172 (1981)

    Article  MathSciNet  Google Scholar 

Download references