Optimal Algorithm for Constructing the Delaunay Triangulation in Ed
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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:60050", author = "V. Tereshchenko and D. Taran", title = "Optimal Algorithm for Constructing the Delaunay Triangulation in Ed", 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.", volume = "6", number = "5", pages = "582-6", }
