О некоторых задачах локализации в триангуляциях Делоне
https://doi.org/10.18255/1818-1015-2012-6-112-126
Аннотация
Рассматриваются постановки задач локализации узлов в триангуляциях Делоне и методы их решения. Для задачи локализации множества узлов предлагается подход, основанный на прослеживании Евклидова минимального остовного дерева триангуляции Делоне. Приводятся и доказываются оценки сложности предложенных методов в среднем и худшем случаях.
Ключевые слова
вычислительная геометрия,
геометрический поиск,
триангуляция Делоне,
слияние перекрывающихся триангуляций,
нерегулярная дискретная сетка,
вычислительная сложность
При поддержке: РФФИ
Об авторе
Наталья Федоровна Дышкант
осковский государственный университет имени М.В. Ломоносова
Россия
НИВЦ, канд. физ.-мат. наук, научный сотрудник
Россия
НИВЦ, канд. физ.-мат. наук, научный сотрудник
Список литературы
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.
Рецензия
Для цитирования:
Дышкант Н.Ф. О некоторых задачах локализации в триангуляциях Делоне. Моделирование и анализ информационных систем. 2012;19(6):112-126. https://doi.org/10.18255/1818-1015-2012-6-112-126
For citation:
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
Просмотров:
938
Послать статью по эл. почте 