ОПТИМАЛЬНЫЕ ДИАГРАММЫ ВОРОНОГО ВЫСШИХ ПОРЯДКОВ ОГРАНИЧЕННЫХ МНОЖЕСТВ И АЛГОРИТМЫ ИХ ПОСТРОЕНИЯ

Main Article Content

Лариса Сергіївна Коряшкіна
Антоніна Павлівна Череватенко

Abstract

Представлены оптимальные диаграммы Вороного высших порядков для ограниченных областей из пространства . Описан подход к построению таких диаграмм, основанный на формулировании и решении непрерывных задач оптимального мультиплексного разбиения множеств с размещением центров при определенных критериях качества разбиения и интегральных ограничениях. Приведены результаты построения диаграмм Вороного  точек-генераторов, оптимально размещенных на ограниченном плоском множестве, при интегральных условиях на их мощности.

Article Details

Section
Applied Mathematics

References

Preparata F., Shamos M. Computational Geometry: An Introduction. (1985) Springer. – 411 p.

Aurenhammer F. Voronoi diagrams – a survey of a fundamental geometric data structure / F. Aurenhammer // ACM Computing Surveys. – 1991. – Vol. 23. – Р. 345 – 405.

Spatial Tessellations: Concepts and Applications of Voronoi Diagrams / A. Okabe, B. Boots, K. Sugihara [et al.] // Chichester, West Sussex: John Wiley & Sons, 2000. – 696 p.

Kiseleva E.M. Theory of Continuous Optimal Set Partitioning Problems as a Universal Mathematical Formalism for Constructing Voronoi Diagrams and Their Generalizations. I. Theoretical Foundations / E. Kiseleva, L. Koriashkina // Cybernetics and Systems Analysis. – 2015. – Vol. 51, Issue 3. – Р. 325 – 335.

Shamos M. Closest-point problems / M. Shamos, D. Hoey // Proc. 16th IEEE Symp. on Foundations of Comput. Sci. – New York, 1975. – Oct. – P. 151 – 162.

Lee D.T. On k-nearest neighbors Voronoi diagrams in the plane / D.T. Lee // IEEE Transactions on Computers. – 1982. – Р. 478 – 487.

Коряшкіна Л.С. Розширення одного класу нескінченновимірних оптимізаційних задач / Л.С. Коряшкіна // Вісник Черкаського університету. – 2015. – № 18 (351). – С. 28 – 36.

Koriashkina L.S. Continuous problems of optimal multiplex-partitioning of sets without constraints and solving methods / L.S. Koriashkina, А.Р. Cherevatenko // Journal of Computational & Applied Mathematics. – 2015. – Vol. 119, N 2. – P. 15 – 32.

Cherevatenko А. On solutions properties of continuous linear problems of optimal multiplex-partitioning of sets without constraints / А. Cherevatenko // Proc. of the 5th International youth science forum “Litteris еt Artibus”, (Lviv, 26–28 November 2015). – Lviv: Lviv Polytechnic Publishing House, 2015. – P. 22 – 25.

Коряшкина Л.С. Непрерывные линейные задачи оптимального мультиплексного разбиения множеств с ограничениями / Л.С. Коряшкина, А.П. Череватенко // Вісник Харківського національного університету ім. В.Н. Каразіна. – (Серія «Математичне моделювання. Інформаційні технології. Автоматизовані системи управління»). – 2015. – Вип. 28. – С. 77 – 91.

Kiseleva E.M. The Theory of Continuous Optimal Set Partitioning Problems as a Universal Mathematical Formalism for Constructing the Voronoi Diagram and its Generalizations. ІI. Algorithms for constructing Voronoi Diagrams based on the theory of optimal partitioning of sets/E.Kiseleva,L.Koriashkina//Cybernetics and Systems Analysis.–2015.–Vol.51,Is.4.–Р3–12

Chazelle B. An improved algorithm for constructing kth-order Voronoi diagrams / B. Chazelle, H. Edelsbrunner // Proc. of the first annual symposium on Computational geometry. – New York: ACM, 1985. – P. 228 – 234.

Rosenberger H. Order-k Voronoi diagrams of sites with additive weights in the plane / H. Rosenberger // Algorithmica. – 1991. – Vol. 6, Issue 1. – P. 490 – 521.

Boots B. Modeling retail trade areas usinghigher-order, multiplicatively weighted Voronoi diagrams / B. Boots, R. South // Journal of Retailing 73. – 1997. – P. 519 – 536.

Meyerhenke H. Constructing Higher-Order Voronoi Diagrams in Parallel / H. Meyerhenke // Proc. of the 21st European Workshop on Computational Geometry, (Eindhoven, 9–11 March 2005). – Eindhoven, 2005. – Р. 123 – 126.

K-Voronoi diagrams computing in arbitrary domains / R. Cardenes, S. Warfield, A. Mewes [et al.] // EEE International Conference on Image Processing (ICIP’03), (Barcelona, 14–17 Sept. 2003). – Barcelona, 2003. – Р. 941 – 944.

Fischer I. Fast Approximation of High-Order Voronoi Diagrams and Distance Transforms on the GPU / I. Fischer, C. Gotsman // J. Graphics Tools. – 2006. – Vol. 4, N 11. – P. 39 – 60.

Cabello S. Higher-order Voronoi diagrams on triangulated surfaces / S. Cabello, M. Fort, J.A. Sellarès // Information Processing Letters. – Vol. 9, N 109. – P. 440 – 445.

Higher Order City Voronoi Diagrams / A. Gemsa, D. Lee, C.H. Liu [et al.] // Helsinki, 2012. – Proc. 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'12).–Lecture Notes in Computer Science.–Vol.7357.–P.59–70.

Lee I. Map segmentation for geospatial data mining through generalized higher-order Voronoi diagrams with sequential scan algorithms / I. Lee, C. Torpelund-Bruin, K. Lee // Expert Systems with Applications. – 2012. – Vol. 39, Issue 12. – P. 11135–11148.

Dong P. Generating and updating multiplicatively weighted Voronoi diagrams for point, line and polygon features in GIS / P.Dong// Computers&Geosciences.–2008.–Vol.34.–Р.411–421.

Lee I. An order-k Voronoi approach to geospatial concept management within conceptual spaces/I.Lee,K.Lee//Applied Artificial Intelligence.–Taylor&Francis Group,2009.–Р.522–537

Boots B. Modeling Retail Trade Areas Using Higher-Order, Mukiplicatively Weighted Voronoi Diagrams/ B. Boots, R. South // Journal of Retailing.–1997.–Vol.4, N73.–P.519–536.

Коряшкина Л.С. Об одном подходе к территориальной сегментации рынка услуг / Л.С. Коряшкина, А.П. Череватенко // Современные информационные и коммуникационные технологии на транспорте, в промышленности и образовании: сб. материалов Междунар. науч.-практ. конф., (Днепропетровск, 16–17 декабря 2015 г.). – Днепропетровск: ДНУЖТ им. В.А. Лазаряна, 2015. – С. 81.

Mashtalir S.V. Stabilization of key frame descriptions with higher order Voronoi diagram / S.V. Mashtalir, O.D. Mikhnova // Бионика интеллекта: науч.-техн. журн. – Х.: Изд-во ХНУРЭ, 2013. – Вып. 1 (80). – С. 68 – 72.

Lin I-J. Extraction of Video Objects via Surface Optimization and Voronoi Order / I. Lin, S. Kung // Journal of VLSI Signal Processing. – 2001. – Vol. 1, N 29. – Р. 23 – 39.

Шор Н.З. Методы минимизации недифференцируемых функций и их приложение / Шор Н.З. – К.: Наукова думка, 1979. – 200 с.

Киселева Е.М. Непрерывные задачи оптимального разбиения множеств и r-алгоритмы / Е.М. Киселева, Л.С. Коряшкина. – К.: Наукова думка, 2015. – 400 с.

Коряшкина Л.С. О способах задания функционала качества в задачах мультиплексного разбиения множеств / Л.С. Коряшкина // Вычислительные методы, модели и образовательные технологии: сб. материалов Междунар. науч.-практ. конф., (Брест, 22 – 23 окт. 2015 г.) / Под общ. ред. О.В. Матысика. – Брест: БрГУ, 2015. – С. 40 – 41.