Preview

Моделирование и анализ информационных систем

Расширенный поиск

О некоторых задачах локализации в триангуляциях Делоне

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

Просмотров: 286


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)