Regular triangulations of dynamic sets of points

ABSTRACT

The Delaunay triangulations of a set of points are a class of triangulations which play an important role in a variety of different disciplines of science. Regular triangulations are a generalization of Delaunay triangulations that maintain both their relationship with convex hulls and with Voronoi diagrams. In regular triangulations, a real value, its weight, is assigned to each point.In this paper a simple data structure is presented that allows regular triangulations of sets of points to be dynamically updated, that is, new points can be incrementally inserted in the set and old points can be deleted from it. The algorithms we propose for insertion and deletion are based on a geometric interpretation of the history data structure in one more dimension and use lifted flips as the unique topological operation. This results in rather simple and efficient algorithms. The algorithms have been implemented and experimental results are given.

REFERENCES

• 1: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 2: Jean-Daniel Boissonnat , Monique Teillaud, On the randomized construction of the Delaunay tree, Theoretical Computer Science, v.112 n.2, p.339-354, May 10, 1993 [doi>10.1016/0304-3975(93)90024-N]
• 3: Siu-Wing Cheng , Tamal K. Dey , Herbert Edelsbrunner , Michael A. Facello , Shang-Hua Teng, Sliver exudation, Proceedings of the fifteenth annual symposium on Computational geometry, p.1-13, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304894]
• 4: Kenneth L. Clarkson , Kurt Mehlhorn , Raimund Seidel, Four results on randomized incremental constructions, Computational Geometry: Theory and Applications, v.3 n.4, p.185-212, Sept. 1993 [doi>10.1016/0925-7721(93)90009-U]
• 5: Olivier Devillers, Improved incremental randomized Delaunay triangulation, Proceedings of the fourteenth annual symposium on Computational geometry, p.106-115, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276896]
• 6: Olivier Devillers, On deletion in Delaunay triangulations, Proceedings of the fifteenth annual symposium on Computational geometry, p.181-188, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304969]
• 7: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 8: H. Edelsbrunner , N. R. Shah, Incremental topological flipping works for regular triangulations, Proceedings of the eighth annual symposium on Computational geometry, p.43-52, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142688]
• 9: Edelsbrunner, H., Waupotitsch, R., 2000. Adaptive simplicial grids from cross-sections of monotone complexes. Internat. J. Comput. Geom. Appl. 10, 267-284.
• 10: Michael A. Facello, Implementation of a randomized algorithm for Delaunay and regular triangulations in three dimensions, Computer Aided Geometric Design, v.12 n.4, p.349-370, June 1995 [doi>10.1016/0167-8396(94)00018-N]
• 11: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 12: Guibas, L.J., Knuth, D.E., Sharir, M., 1992. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica 7, 381-413.
• 13: Barry Joe, Construction of three-dimensional Delaunay triangulations using local transformations, Computer Aided Geometric Design, v.8 n.2, p.123-142, May 1991 [doi>10.1016/0167-8396(91)90038-D]
• 14: Lawson, C.L., 1977. Software for C1 surface interpolation, in: Rice, J.R. (Ed.), Mathematical Software III. Academic Press, pp. 161-194.
• 15: Tomonari Masada , Hiroshi Imai , Keiko Imai, Enumeration of regular triangulations, Proceedings of the twelfth annual symposium on Computational geometry, p.224-233, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237373]
• 16: Ketan Mulmuley, Randomized multidimensional search trees: lazy balancing and dynamic shuffling (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.180-196, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185368]
• 17: Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992
• 18: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985

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

Keywords:
Delaunay and regular triangulations, Voronoi diagrams, convex hulls, incremental algorithms