About Some Localization Problems in Delaunay Triangulations

N. F. Dyshkant

Modelirovanie i analiz informacionnyh sistem, Tome 19 (2012) no. 6, pp. 112-126.

Résumé

We study some problems of nodes localization in a Delaunay triangulation and problem-solving procedures. For the problem of the set of nodes the computationally efficient approach that uses Euclidean minimum spanning tree of Delaunay triangulation is proposed. Efficient estimations for computational comlexity of the proposed methods in the average and in the worst cases are proved.

Détail

Keywords: computational geometry, geometric search, merging of overlapping triangulations, unregular discrete mesh, computational complexity.
Mots-clés : Delaunay triangulation

Bibliographie

[1] A. V. Skvortsov, “Obzor algoritmov postroeniya triangulyatsii Delone”, Vychislitelnye metody i programmirovanie, 2002, no. 3, 14–39 | MR

[2] D. G. Kirkpatrik, “Optimal search in planar subdivisions”, SIAM J. Comput., 12:1 (1983), 28–35 | MR

[3] I. Haran, D. Helperin, “An Experimental Study of Point Location in Planar Arrangements in Cgal”, ACM Journal of Experimental Algorithms, 13:3 (2009), 1–31

[4] O. Devillers, S. Pion, M. Teillaud, “Walking in a triangulation”, Internat. J. Found. Comput. Sci., 13 (2002), 181–199 | MR | Zbl

[5] E. Mucke, I. Saias, B. Zhu, “Fast Randomized Point Location Without Preprocessing in Two- And Three-dimensional Delaunay Triangulations”, Proceedings of the 11th Annual Symposium on Computational Geometry, 1996, 274–283

[6] L. Devroye, E. P. Mucke, B. Zhu, “A note on point location in Delaunay triangulations of random points”, Algorithmica, 22 (1998), 477–482 | MR | Zbl

[7] L. Devroye, C. Lemaire, J. Moreau, “Expected time analysis for Delaunay point location”, Computational geometry, 29:2 (2004), 61–89 | MR | Zbl

[8] A. V. Skvortsov, Yu. L. Kostyuk, “Effektivnye algoritmy postroeniya triangulyatsii Delone”, Geoinformatika. Teoriya i praktika, 1998, no. 1, 22–47 | MR

[9] M. Shapiro, “A note on Lee and Schachter’s algorithm for Delaunay triangulation”, Inter. Jour. of Comp. and Inf. Sciences, 10:6 (1981), 413–418 | MR

[10] D. Cheriton, R. E. Tarjan, “Finding minimum spanning trees”, SIAM J. Comput., 5:4 (1976), 724–742 | MR | Zbl

[11] Yu. L. Kostyuk, “Graficheskii poisk s ispolzovaniem triangulyatsii i kletochnogo razbieniya”, Vestnik Tomskogo gos. un-ta, 2002, no. 275, 147–152

[12] P. Bose, L. Devroye, “Intersections with Random Geometric Objects”, Computational Geometry: Theory and Applications, 10:3 (1998), 139–154 | MR | Zbl

[13] L. M. Mestetskii, E. V. Tsarik, “Triangulyatsiya Delone: rekursiya bez prostranstvennogo razdeleniya tochek”, GrafiKon’2004, Trudy mezhdunarodnoi konferentsii po kompyuternoi grafike i mashinnomu zreniyu, MGU, M., 2004, 267–270

[14] L. M. Mestetskii, E. V. Tsarik, “Sliyanie nerazdelennykh triangulyatsii Delone”, Slozhnye sistemy: obrabotka informatsii, modelirovanie i optimizatsiya, Sbornik nauchnykh trudov, v. 2, Tverskoi gos. universitet, Tver, 2004, 216–231

[15] N. F. Dyshkant, “Mery dlya sravneniya diskretnykh modelei odnoznachnykh poverkhnostei”, Vestnik Moskovskogo universiteta. Seriya 15. Vychislitelnaya matematika i kibernetika, 4 (2011), 41–48 | MR | Zbl

[16] N. Dyshkant, “Measures for Surface Comparison on Unstructured Grids with Different Density”, Discrete Geometry for Computer Imagery, Lecture Notes in Computer Science, 6607, 2011, 501–512 | Zbl