Optimal Algorithm for Constructing the Delaunay Triangulation in Ed

Authors: V. Tereshchenko, D. Taran

Abstract:

In this paper we propose a new approach to constructing the Delaunay Triangulation and the optimum algorithm for the case of multidimensional spaces (d ≥ 2). Analysing the modern state, it is possible to draw a conclusion, that the ideas for the existing effective algorithms developed for the case of d ≥ 2 are not simple to generalize on a multidimensional case, without the loss of efficiency. We offer for the solving this problem an effective algorithm that satisfies all the given requirements. But theoretical complexity of the problem it is impossible to improve as the Worst - Case Optimality for algorithms of solving such a problem is proved.

Keywords: Delaunay triangulation, multidimensional space, Voronoi Diagram, optimal algorithm.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1076454

References:

[1] J.E. Goodman and J. O-Rourke, eds. Handbook of Discrete and Computational Geometry. Second Edition, Chapman and Hall/CRC Press, 2004.
[2] P. Cignoni, C. Montani, R. Scopigno. DeWall: A Fast Divide and Conquer Delaunay Triangulation Algorithm in Ed. Computer-Aided Design Vol. 30 (5):333-341, 1998.
[3] M. de Berg, O. Cheong, M.van Kreveld, M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, 2008.
[4] L. Guibas, D. Knuth, M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica 7:381-413,1992.
[5] H. Edelsbrunner, S. Nimish. Incremental Topological Flipping Works for Regular Triangulations. Algorithmica 15 (3): 223-241,1996.
[6] M. Caroli, M. Teillaud. Delaunay triangulations of point sets in closed euclidean d-manifolds. In Proc. of the 27th annual ACM symposium on Computational geometry, pages 274-282, 2011.
[7] M. Hoffmann., Y. Okamoto. The minimum weight triangulation problem with few inner points. Computational Geometry. 34 (3):149-158, 2006.
[8] J. Gudmundsson, H. Haverkort, and M. van Kreveld. Constrained higher order Delaunay triangulations. Comput.Geom. Theory Appl., 30:271- 277, 2005.
[9] R.I. Silveira, M. van Kreveld. Towards a Definition of Higher Order Constrained Delaunay Triangulations. In proc. 19th Canadian Conference on Computational Geometry, pages 322-337, 2007.
[10] T. de Kok, M. van Kreveld and M. L¨offler. Generating realistic terrains with higher-order Delaunay triangulations. Comput. Geom. Theory Appl., 36:52-65,2007.
[11] S. Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2:153-174,1987.
[12] C.B. Barber, D.P. Dobkin, and H.T. Huhdanpaa. The Quickhull algorithm for convex hulls. ACM Trans. on Mathematical Software, 22(4):469-483, 1996.
[13] F. Preparata and M.I. Shamos. Computational Geometry: An introduction. Springer-Verlag, Berlin, 1985.
[14] D. R. Chand and S. S. Kapur. An algorithm for convex polytopes. JASM 17(1): 78-86, 1970.
[15] J. L. Bentley. Muldimensional binary search trees used for associative searching. Communications of the ACM 18: 509-517, 1975.