Алгоритм построения диаграмм Вороного с оптимальным размещением точек–генераторов на основе теории оптимального разбиения множеств - Киселева, Е.М.; Гарт, Л.Л.; Притоманова, О.М. (Проблемы управления и информатики, 2020)
Запропоновано алгоритм побудови узагальненої діаграми Вороного з оптимальним розміщенням скінченної кількості точок–генераторів в обмеженій множині n-вимірного евклідового простору. Алгоритм заснований на формулюванні відповідної неперервної задачі оптимального розбиття множин з критерієм якості розбиття, що забезпечує відповідний вид діаграми Вороного, і застосуванні для її розв’язання апарату теорії оптимального розбиття. При цьому для чисельного розв’язання допоміжної задачі скінченновимірної оптимізації, що виникає при розробці методу розв'язання згаданої нескінченновимірної задачі оптимального розбиття множин, використаний ефективний метод недиференційовної оптимізації — один з варіантів методу узагальненого градієнтного спуску з розтягуванням простору в напрямку різниці двох послідовних узагальнених антиградієнтів (r-алгоритм Шора). Запропонований у роботі алгоритм побудови узагальненої діаграми Вороного з оптимальним розміщенням скінченної кількості точок–генераторів в обмеженій множині n-мірного евклідового простору має ряд переваг порівняно з відомими: він не залежить від розмірності евклідового простору, що містить вихідну обмежену множину; застосовний для задач великих розмірностей (понад 300 точок–генераторів); зберігає силу не тільки для евклідових метрик, але і для метрик Чебишева, манхеттенської та інших; складність реалізації алгоритму побудови діаграми Вороного на основі запропонованого підходу не збільшується при збільшенні кількості точок–генераторів. Представлено результати програмної реалізації розробленого алгоритму для побудови стандартної діаграми Вороного з оптимальним розміщенням точок–генераторів, а також деяких її узагальнень, таких як адитивна, мультиплікативна та адитивномультиплікативна діаграми Вороного з оптимальним розміщенням точок– генераторів.