5.7. РОЗВ'ЯЗАННЯ ЗАДАЧ ПРО БЛИЗКІСТЬ ЗА ДОПОМОГОЮ ДІАГРАМИ ВОРОНОГО.
Теорема 5.15Задача УСІ НАЙБЛИЖЧІ СУСІДИ
зводима за лінійний час до задачі ДІАГРАМА ВОРОНОГО, і тому її можна розв'язати за оптимальний час Q (NlogN). Доведення. Згідно з теореми 5.3 кожний
найближчий сусід точки рі визначає ребро
многокутника V(i). Щоб знайти найближчого сусіда точки
рі, достатньо переглянути кожне ребро многокутника
V(i). Так як кожне ребро належить двом многокутникам Вороного,
ребра не переглядатимуться більше двох разів. Теорема 5.16Задача НАЙБЛИЖЧА ПАРА зводима
за лінійний час до задачі ДІАГРАМА ВОРОНОГО, і тому її можна розв'язати за оптимальний
час Q(NlogN).
Доведення зводиться до використання зводимості задачі НАЙБЛИЖЧА ПАРА до задачі УСІ НАЙБЛИЖЧІ СУСІДИ. Теорема 5.17Пошук найближчого сусіда
можна виконати за оптимальний час О(logN), використовуючи пам'ять
об'ємом О(N), з витратами на попередню обробку О(NlogN). Доведення: Побудова ДВ - О(NlogN),
тоді застосовуються теореми про локалізацію точки. Теорема 5.18Тріангуляцію, в якій коло,
описане навколо будь-якого трикутника, не містить інших точок, можна побудувати
за оптимальний час Q(NlogN). Теорема 5.19Якщо для множини точок
побудована ДВ, то опуклу оболонку можна побудувати за лінійний час. Зв'язок задач про близкість можна зобразити у вигляді наступної діаграми.
Мал. 5.21. Зв'язок задач про близкість з основними задачами,
які використовуються як обчислювальні прототипи.
