Терещенко В. М. Побудова тріангуляції Делоне для планарних графів / В. М. Терещенко // Вісн. Київ. нац. ун-ту. Сер. Фіз.-мат. науки. - 2014. - Вип. 2. - С. 206-209. - Бібліогр.: 6 назв. - укp.Розглянуто метод перевірки можливості побудови тріангуляції Делоне планарного графа зі складністю, не гіршою за O(N<^>2). Під час аналізу задачі розглядались дві головні задачі. Перша задача полягає у можливості додавання нових точок у триангуляцію, що фактично зводиться до побудови тріангуляції, в якій на окремі трикутники можуть накладатися певні обмеження під час дослідження. Друга задача полягає у побудові тріангуляції Делоне для області з дірками так, щоб жодне з ребер триангуляції не перетинало границь області. Під час вирішення першої задачі запропоновано контр-приклад, який вказує на те, що не для кожного планарного графа існує тріангуляція Делоне. Для розв'язання другої задачі запропоновано метод, який базується на інкрементальному алгоритмі побудови тріангуляції Делоне і надає змогу одержати алгоритм із загальною оцінкою складності O(N<^>2). Індекс рубрикатора НБУВ: В126.3
Рубрики:
Шифр НБУВ: Ж28079/фіз.-мат. Пошук видання у каталогах НБУВ Додаткова інформація про автора(ів) публікації: (cписок формується автоматично, до списку можуть бути включені персоналії з подібними іменами або однофамільці) ![](/irbis_nbuv/images/info.png) Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"
|