maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2012-6-112-126mais-145Research ArticleОригинальные статьиArticlesО некоторых задачах локализации в триангуляциях ДелонеAbout Some Localization Problems in Delaunay TriangulationsДышкантНаталья ФедоровнаDyshkantN. F.

НИВЦ, канд. физ.-мат. наук, научный сотрудник

НИВЦ, канд. физ.-мат. наук, научный сотрудник

natalia.dyshkant@gmail.comосковский государственный университет имени М.В. ЛомоносоваРоссияМосковский государственный университет имени М.В. ЛомоносоваRussian Federation201212032015196112126Copyright © Дышкант Н.Ф., 20152015Дышкант Н.Ф.Dyshkant N.F.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/145

Рассматриваются постановки задач локализации узлов в триангуляциях Делоне и методы их решения. Для задачи локализации множества узлов предлагается подход, основанный на прослеживании Евклидова минимального остовного дерева триангуляции Делоне. Приводятся и доказываются оценки сложности предложенных методов в среднем и худшем случаях.

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

вычислительная геометриягеометрический поисктриангуляция Делонеслияние перекрывающихся триангуляцийнерегулярная дискретная сеткавычислительная сложностьcomputational geometrygeometric searchDelaunay triangulationmerging of overlapping triangulationsunregular discrete meshcomputational complexityРФФИReferencesСкворцов А. В. Обзор алгоритмов построения триангуляции Делоне // Вычислительные методы и программирование. 2002. № 3. С. 14–39.Скворцов А. В. Обзор алгоритмов построения триангуляции Делоне // Вычислительные методы и программирование. 2002. № 3. С. 14–39.Kirkpatrik D. G. Optimal search in planar subdivisions // SIAM J. Comput. 1983. Vol. 12, № 1. P. 28–35.Kirkpatrik D. G. Optimal search in planar subdivisions // SIAM J. Comput. 1983. Vol. 12, № 1. P. 28–35.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.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.Devillers O., Pion S., Teillaud M. Walking in a triangulation // Internat. J. Found. Comput. Sci. 2002. 13. P. 181–199.Devillers O., Pion S., Teillaud M. Walking in a triangulation // Internat. J. Found. Comput. Sci. 2002. 13. P. 181–199.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.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.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.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.Devroye L., Lemaire C., Moreau J. Expected time analysis for Delaunay point location // Computational geometry. 2004. Vol. 29, № 2. P. 61–89.Devroye L., Lemaire C., Moreau J. Expected time analysis for Delaunay point location // Computational geometry. 2004. Vol. 29, № 2. P. 61–89.Скворцов А. В., Костюк Ю. Л. Эффективные алгоритмы построения триангуляции Делоне // Геоинформатика. Теория и практика. Томск: Изд–во Томского ун-та, 1998. № 1. С. 22–47.Скворцов А. В., Костюк Ю. Л. Эффективные алгоритмы построения триангуляции Делоне // Геоинформатика. Теория и практика. Томск: Изд–во Томского ун-та, 1998. № 1. С. 22–47.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.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.Cheriton D., Tarjan R. E. Finding minimum spanning trees // SIAM J. Comput. 1976. Vol. 5, № 4. P. 724–742.Cheriton D., Tarjan R. E. Finding minimum spanning trees // SIAM J. Comput. 1976. Vol. 5, № 4. P. 724–742.Костюк Ю. Л. Графический поиск с использованием триангуляции и клеточного разбиения // Вестник Томского гос. ун-та. 2002. № 275. С. 147–152.Костюк Ю. Л. Графический поиск с использованием триангуляции и клеточного разбиения // Вестник Томского гос. ун-та. 2002. № 275. С. 147–152.Bose P., Devroye L. Intersections with Random Geometric Objects // Computational Geometry: Theory and Applications. 1998. Vol, 10, № 3. P. 139–154.Bose P., Devroye L. Intersections with Random Geometric Objects // Computational Geometry: Theory and Applications. 1998. Vol, 10, № 3. P. 139–154.Местецкий Л. М., Царик Е. В. Триангуляция Делоне: рекурсия без пространственного разделения точек // Труды международной конференции по компьютерной графике и машинному зрению ГрафиКон’2004. М.: МГУ, 2004. С. 267–270.Местецкий Л. М., Царик Е. В. Триангуляция Делоне: рекурсия без пространственного разделения точек // Труды международной конференции по компьютерной графике и машинному зрению ГрафиКон’2004. М.: МГУ, 2004. С. 267–270.Местецкий Л. М., Царик Е. В. Слияние неразделённых триангуляций Делоне // Сложные системы: обработка информации, моделирование и оптимизация: Сборник научных трудов. Тверь: Тверской гос. университет, 2004. Вып. 2. С. 216–231.Местецкий Л. М., Царик Е. В. Слияние неразделённых триангуляций Делоне // Сложные системы: обработка информации, моделирование и оптимизация: Сборник научных трудов. Тверь: Тверской гос. университет, 2004. Вып. 2. С. 216–231.Дышкант Н. Ф. Меры для сравнения дискретных моделей однозначных поверхностей // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2011. T. №4. С. 41–48.Дышкант Н. Ф. Меры для сравнения дискретных моделей однозначных поверхностей // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2011. T. №4. С. 41–48.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.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.

The authors declare that there are no conflicts of interest present.