Kotsur D. V. An algorithm for Lp-Voronoi diagram construction on discrete grid in 2D = Алгоритм побудови діаграми Вороного на двовимірній сітці з Lp нормою / D. V. Kotsur // Вісн. Київ. нац. ун-ту. Сер. Фіз.-мат. науки. - 2017. - Вип. 4. - С. 95-98. - Бібліогр.: 8 назв. - англ.Досліджено алгоритм побудови апроксимації діаграми Вороного на двовимірній решітці з Lp нормою. Ініціалізація алгоритму відбувається шляхом відображення вхідного набору точок на двовимірну решітку. В основі алгоритму побудови діаграми Вороного лежить процес еволюції кіл з центрами, що відповідають координатам вхідних точок, на двовимірній сітці з Lp нормою. На першому кроці радіуси кіл дорівнюють 0, тобто кола співпадають з вхідним набором точок. Далі відбувається рівномірне збільшення радіусів кіл, перетини яких у процесі еволюції визначають ребра і вершини діаграми Вороного. Аналіз складності алгоритму показав, що діаграма Вороного може бути побудована за час O(N), де N - це розмір двовимірної сітки. Проведено числові експерименти з побудови апроксимованої діаграми Вороного в Lp для значень p рівних 1 (манхеттенська метрика), 1.5, 2.0 (евклідова метрика), 5.0, inf. Модифікація представленого алгоритму знаходить застосування в задачах обробки зображень. Наприклад, врахування контурів зображення у процесі еволюції діаграми Вороного надає сегментацію вхідного зображення шляхом розбиття на суперпікселі. Індекс рубрикатора НБУВ: В171.5 + З970.632
Рубрики:
Шифр НБУВ: Ж28079/фіз.-мат. Пошук видання у каталогах НБУВ
Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"
|