Алгоритм построения диаграмм Вороного с оптимальным размещением точек–генераторов на основе теории оптимального разбиения множеств
Запропоновано алгоритм побудови узагальненої діаграми Вороного з оптимальним розміщенням скінченної кількості точок–генераторів в обмеженій множині n-вимірного евклідового простору. Алгоритм заснований на формулюванні відповідної неперервної задачі оптимального розбиття множин з критерієм якості роз...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2020 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/208707 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Алгоритм построения диаграмм Вороного с оптимальным размещением точек–генераторов на основе теории оптимального разбиения множеств / Е.М. Киселева, Л.Л. Гарт, О.М. Притоманова // Проблемы управления и информатики. — 2020. — № 2. — С. 5-15. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862719842988064768 |
|---|---|
| author | Киселева, Е.М. Гарт, Л.Л. Притоманова, О.М. |
| author_facet | Киселева, Е.М. Гарт, Л.Л. Притоманова, О.М. |
| citation_txt | Алгоритм построения диаграмм Вороного с оптимальным размещением точек–генераторов на основе теории оптимального разбиения множеств / Е.М. Киселева, Л.Л. Гарт, О.М. Притоманова // Проблемы управления и информатики. — 2020. — № 2. — С. 5-15. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Запропоновано алгоритм побудови узагальненої діаграми Вороного з оптимальним розміщенням скінченної кількості точок–генераторів в обмеженій множині n-вимірного евклідового простору. Алгоритм заснований на формулюванні відповідної неперервної задачі оптимального розбиття множин з критерієм якості розбиття, що забезпечує відповідний вид діаграми Вороного, і застосуванні для її розв’язання апарату теорії оптимального розбиття. При цьому для чисельного розв’язання допоміжної задачі скінченновимірної оптимізації, що виникає при розробці методу розв'язання згаданої нескінченновимірної задачі оптимального розбиття множин, використаний ефективний метод недиференційовної оптимізації — один з варіантів методу узагальненого градієнтного спуску з розтягуванням простору в напрямку різниці двох послідовних узагальнених антиградієнтів (r-алгоритм Шора). Запропонований у роботі алгоритм побудови узагальненої діаграми Вороного з оптимальним розміщенням скінченної кількості точок–генераторів в обмеженій множині n-мірного евклідового простору має ряд переваг порівняно з відомими: він не залежить від розмірності евклідового простору, що містить вихідну обмежену множину; застосовний для задач великих розмірностей (понад 300 точок–генераторів); зберігає силу не тільки для евклідових метрик, але і для метрик Чебишева, манхеттенської та інших; складність реалізації алгоритму побудови діаграми Вороного на основі запропонованого підходу не збільшується при збільшенні кількості точок–генераторів. Представлено результати програмної реалізації розробленого алгоритму для побудови стандартної діаграми Вороного з оптимальним розміщенням точок–генераторів, а також деяких її узагальнень, таких як адитивна, мультиплікативна та адитивномультиплікативна діаграми Вороного з оптимальним розміщенням точок– генераторів.
An algorithm is proposed for constructing a generalized Voronoi diagram with optimal placement of a finite number of generator points in a bounded set of n-dimensional Euclidean space. The algorithm is based on the formulation of the corresponding continuous problem of optimal set partitioning with a partition quality criterion providing the corresponding form of the Voronoi diagram, and on the application of the apparatus of the optimal partitioning theory to solve this problem. Herewith, the effective method of non-differentiable optimization is used for the numerical solution of an auxiliary finite-dimensional optimization problem arising in the development of the method for solving the mentioned infinite-dimensional optimal partitioning problem. Namely, that is one of the variants of the generalized gradient descent method with space expansion in the direction of the difference of two successive generalized antigradients (Shor’s r-algorithm). The proposed algorithm for constructing a generalized Voronoi diagram with optimal placement of a finite number of generator points in a bounded set of n-dimensional Euclidean space has some advantages compared to those known in the scientific literature. It does not depend on the dimension of Euclidean space containing the original bounded set; it is applicable for large-scale problems (over 300 generator points); it works not only for Euclidean metrics, but also for Chebyshev, Manhattan and other ones; the complexity of the algorithm implementation for constructing a Voronoi diagram based on the proposed approach does not increase with an increase in the number of generator points. The results of software implementation of the developed algorithm are presented for constructing a standard Voronoi diagram with optimal placement of generator points, as well as some of its generalizations, such as additive, multiplicative and additive-multiplicative Voronoi diagrams with optimal placement of generator points.
|
| first_indexed | 2025-12-07T18:22:38Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-208707 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T18:22:38Z |
| publishDate | 2020 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Киселева, Е.М. Гарт, Л.Л. Притоманова, О.М. 2025-11-04T16:04:01Z 2020 Алгоритм построения диаграмм Вороного с оптимальным размещением точек–генераторов на основе теории оптимального разбиения множеств / Е.М. Киселева, Л.Л. Гарт, О.М. Притоманова // Проблемы управления и информатики. — 2020. — № 2. — С. 5-15. — Бібліогр.: 8 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208707 519.8 10.1615/JAutomatInfScien.v52.i3.10 Запропоновано алгоритм побудови узагальненої діаграми Вороного з оптимальним розміщенням скінченної кількості точок–генераторів в обмеженій множині n-вимірного евклідового простору. Алгоритм заснований на формулюванні відповідної неперервної задачі оптимального розбиття множин з критерієм якості розбиття, що забезпечує відповідний вид діаграми Вороного, і застосуванні для її розв’язання апарату теорії оптимального розбиття. При цьому для чисельного розв’язання допоміжної задачі скінченновимірної оптимізації, що виникає при розробці методу розв'язання згаданої нескінченновимірної задачі оптимального розбиття множин, використаний ефективний метод недиференційовної оптимізації — один з варіантів методу узагальненого градієнтного спуску з розтягуванням простору в напрямку різниці двох послідовних узагальнених антиградієнтів (r-алгоритм Шора). Запропонований у роботі алгоритм побудови узагальненої діаграми Вороного з оптимальним розміщенням скінченної кількості точок–генераторів в обмеженій множині n-мірного евклідового простору має ряд переваг порівняно з відомими: він не залежить від розмірності евклідового простору, що містить вихідну обмежену множину; застосовний для задач великих розмірностей (понад 300 точок–генераторів); зберігає силу не тільки для евклідових метрик, але і для метрик Чебишева, манхеттенської та інших; складність реалізації алгоритму побудови діаграми Вороного на основі запропонованого підходу не збільшується при збільшенні кількості точок–генераторів. Представлено результати програмної реалізації розробленого алгоритму для побудови стандартної діаграми Вороного з оптимальним розміщенням точок–генераторів, а також деяких її узагальнень, таких як адитивна, мультиплікативна та адитивномультиплікативна діаграми Вороного з оптимальним розміщенням точок– генераторів. An algorithm is proposed for constructing a generalized Voronoi diagram with optimal placement of a finite number of generator points in a bounded set of n-dimensional Euclidean space. The algorithm is based on the formulation of the corresponding continuous problem of optimal set partitioning with a partition quality criterion providing the corresponding form of the Voronoi diagram, and on the application of the apparatus of the optimal partitioning theory to solve this problem. Herewith, the effective method of non-differentiable optimization is used for the numerical solution of an auxiliary finite-dimensional optimization problem arising in the development of the method for solving the mentioned infinite-dimensional optimal partitioning problem. Namely, that is one of the variants of the generalized gradient descent method with space expansion in the direction of the difference of two successive generalized antigradients (Shor’s r-algorithm). The proposed algorithm for constructing a generalized Voronoi diagram with optimal placement of a finite number of generator points in a bounded set of n-dimensional Euclidean space has some advantages compared to those known in the scientific literature. It does not depend on the dimension of Euclidean space containing the original bounded set; it is applicable for large-scale problems (over 300 generator points); it works not only for Euclidean metrics, but also for Chebyshev, Manhattan and other ones; the complexity of the algorithm implementation for constructing a Voronoi diagram based on the proposed approach does not increase with an increase in the number of generator points. The results of software implementation of the developed algorithm are presented for constructing a standard Voronoi diagram with optimal placement of generator points, as well as some of its generalizations, such as additive, multiplicative and additive-multiplicative Voronoi diagrams with optimal placement of generator points. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы оптимизации и оптимальное управление Алгоритм построения диаграмм Вороного с оптимальным размещением точек–генераторов на основе теории оптимального разбиения множеств Алгоритм побудови діаграм Вороного з оптимальним розміщенням точок–генераторів на основі теорії оптимального розбиття множин An algorithm to construct Voronoi diagrams with optimal placement of generator points based on the theory of optimal set partitioning Article published earlier |
| spellingShingle | Алгоритм построения диаграмм Вороного с оптимальным размещением точек–генераторов на основе теории оптимального разбиения множеств Киселева, Е.М. Гарт, Л.Л. Притоманова, О.М. Методы оптимизации и оптимальное управление |
| title | Алгоритм построения диаграмм Вороного с оптимальным размещением точек–генераторов на основе теории оптимального разбиения множеств |
| title_alt | Алгоритм побудови діаграм Вороного з оптимальним розміщенням точок–генераторів на основі теорії оптимального розбиття множин An algorithm to construct Voronoi diagrams with optimal placement of generator points based on the theory of optimal set partitioning |
| title_full | Алгоритм построения диаграмм Вороного с оптимальным размещением точек–генераторов на основе теории оптимального разбиения множеств |
| title_fullStr | Алгоритм построения диаграмм Вороного с оптимальным размещением точек–генераторов на основе теории оптимального разбиения множеств |
| title_full_unstemmed | Алгоритм построения диаграмм Вороного с оптимальным размещением точек–генераторов на основе теории оптимального разбиения множеств |
| title_short | Алгоритм построения диаграмм Вороного с оптимальным размещением точек–генераторов на основе теории оптимального разбиения множеств |
| title_sort | алгоритм построения диаграмм вороного с оптимальным размещением точек–генераторов на основе теории оптимального разбиения множеств |
| topic | Методы оптимизации и оптимальное управление |
| topic_facet | Методы оптимизации и оптимальное управление |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/208707 |
| work_keys_str_mv | AT kiselevaem algoritmpostroeniâdiagrammvoronogosoptimalʹnymrazmeŝeniemtočekgeneratorovnaosnoveteoriioptimalʹnogorazbieniâmnožestv AT gartll algoritmpostroeniâdiagrammvoronogosoptimalʹnymrazmeŝeniemtočekgeneratorovnaosnoveteoriioptimalʹnogorazbieniâmnožestv AT pritomanovaom algoritmpostroeniâdiagrammvoronogosoptimalʹnymrazmeŝeniemtočekgeneratorovnaosnoveteoriioptimalʹnogorazbieniâmnožestv AT kiselevaem algoritmpobudovidíagramvoronogozoptimalʹnimrozmíŝennâmtočokgeneratorívnaosnovíteorííoptimalʹnogorozbittâmnožin AT gartll algoritmpobudovidíagramvoronogozoptimalʹnimrozmíŝennâmtočokgeneratorívnaosnovíteorííoptimalʹnogorozbittâmnožin AT pritomanovaom algoritmpobudovidíagramvoronogozoptimalʹnimrozmíŝennâmtočokgeneratorívnaosnovíteorííoptimalʹnogorozbittâmnožin AT kiselevaem analgorithmtoconstructvoronoidiagramswithoptimalplacementofgeneratorpointsbasedonthetheoryofoptimalsetpartitioning AT gartll analgorithmtoconstructvoronoidiagramswithoptimalplacementofgeneratorpointsbasedonthetheoryofoptimalsetpartitioning AT pritomanovaom analgorithmtoconstructvoronoidiagramswithoptimalplacementofgeneratorpointsbasedonthetheoryofoptimalsetpartitioning |