About Some Localization Problems in Delaunay Triangulations
https://doi.org/10.18255/1818-1015-2012-6-112-126
Abstract
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.
computational geometry, geometric search, Delaunay triangulation, merging of overlapping triangulations, unregular discrete mesh, computational complexity
About the Author
N. F. Dyshkant
Московский государственный университет имени М.В. Ломоносова
Russian Federation
НИВЦ, канд. физ.-мат. наук, научный сотрудник
Russian Federation
НИВЦ, канд. физ.-мат. наук, научный сотрудник
References
1. Скворцов А. В. Обзор алгоритмов построения триангуляции Делоне // Вычислительные методы и программирование. 2002. № 3. С. 14–39.
2. Kirkpatrik D. G. Optimal search in planar subdivisions // SIAM J. Comput. 1983. Vol. 12, № 1. P. 28–35.
3. Haran I., Helperin D. An Experimental Study of Point Location in Planar Arrangements in Cgal // ACM Journal of Experimental Algorithms. 2009. Vol. 13, № 3. P. 1–31.
4. Devillers O., Pion S., Teillaud M. Walking in a triangulation // Internat. J. Found. Comput. Sci. 2002. 13. P. 181–199.
5. Mucke E., Saias I., Zhu B. Fast Randomized Point Location Without Preprocessing in Two- And Three-dimensional Delaunay Triangulations // Proceedings of the 11th Annual Symposium on Computational Geometry. 1996. P. 274–283.
6. Devroye L., Mucke E. P., Zhu B. A note on point location in Delaunay triangulations of random points // Algorithmica. 1998. Vol. 22. P. 477–482.
7. Devroye L., Lemaire C., Moreau J. Expected time analysis for Delaunay point location // Computational geometry. 2004. Vol. 29, № 2. P. 61–89.
8. Скворцов А. В., Костюк Ю. Л. Эффективные алгоритмы построения триангуляции Делоне // Геоинформатика. Теория и практика. Томск: Изд–во Томского ун-та, 1998. № 1. С. 22–47.
9. Shapiro M. A note on Lee and Schachter’s algorithm for Delaunay triangulation // Inter. Jour. of Comp. and Inf. Sciences. 1981. Vol. 10, № 6. P. 413–418.
10. Cheriton D., Tarjan R. E. Finding minimum spanning trees // SIAM J. Comput. 1976. Vol. 5, № 4. P. 724–742.
11. Костюк Ю. Л. Графический поиск с использованием триангуляции и клеточного разбиения // Вестник Томского гос. ун-та. 2002. № 275. С. 147–152.
12. Bose P., Devroye L. Intersections with Random Geometric Objects // Computational Geometry: Theory and Applications. 1998. Vol, 10, № 3. P. 139–154.
13. Местецкий Л. М., Царик Е. В. Триангуляция Делоне: рекурсия без пространственного разделения точек // Труды международной конференции по компьютерной графике и машинному зрению ГрафиКон’2004. М.: МГУ, 2004. С. 267–270.
14. Местецкий Л. М., Царик Е. В. Слияние неразделённых триангуляций Делоне // Сложные системы: обработка информации, моделирование и оптимизация: Сборник научных трудов. Тверь: Тверской гос. университет, 2004. Вып. 2. С. 216–231.
15. Дышкант Н. Ф. Меры для сравнения дискретных моделей однозначных поверхностей // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2011. T. №4. С. 41–48.
16. Dyshkant N. Measures for Surface Comparison on Unstructured Grids with Different Density // Lecture Notes in Computer Science: Discrete Geometry for Computer Imagery. 2011. Vol. 6607. P. 501–512.
Review
For citations:
Dyshkant N.F. About Some Localization Problems in Delaunay Triangulations. Modeling and Analysis of Information Systems. 2012;19(6):112-126. (In Russ.) https://doi.org/10.18255/1818-1015-2012-6-112-126
Views:
945
Email this article 