Досліджено алгоритм побудови апроксимації діаграми Вороного на двовимірній решітці з L_p нормою. Ініціалізація алгоритму відбувається шляхом відображення вхідного набору точок на двовимірну решітку. В основі алгоритму побудови діаграми Вороного лежить процес еволюції кіл з центрами, що відповідають координатам вхідних точок, на двовимірній сітці з L_p нормою. На першому кроці радіуси кіл дорівнюють 0, тобто кола співпадають з вхідним набором точок. Далі відбувається рівномірне збільшення радіусів кіл, перетини яких у процесі еволюції визначають ребра і вершини діаграми Вороного. Аналіз складності алгоритму показав, що діаграма Вороного може бути побудована за час O(N), де N - це розмір двовимірної сітки. Проведено числові експерименти з побудови апроксимованої діаграми Вороного в L_p для значень p рівних 1 (манхеттенська метрика), 1.5, 2.0 (евклідова метрика), 5.0, inf. Модифікація представленого алгоритму знаходить застосування в задачах обробки зображень. Наприклад, врахування контурів зображення у процесі еволюції діаграми Вороного надає сегментацію вхідного зображення шляхом розбиття на суперпікселі.

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"