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

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

Abstract


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

Keywords


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

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.


Full Text: PDF (Українська)

Refbacks

  • There are currently no refbacks.
Archive
2014 18 38
2015 18 38
2016 1-2  

User

Journal Content

Browse

Language