Граф відно́сних о́колів — це неорієнтований граф, визначений на множині точок на евклідовій площині з'єднанням двох точок p і q ребом тоді, коли не існує третьої точки r, яка ближче як до p, так і до q, ніж p і q одна до одної. Цей граф 1980 року запропонував як спосіб визначення на множині точок структури, яка відбиває людське сприйняття форми множини.
Алгоритми Суповіт показав, як ефективно побудувати граф відносних околів за час O(n log n). Граф можна обчислити за середній час O (n) для довільної множини точок, рівномірно розподілених у одиничному квадраті. Граф відносних околів можна обчислити за лінійний час із тріангуляції Делоне множини точок.
Узагальнення Оскільки граф визначений лише в термінах відстаней між точками, граф відносних околів можна визначити для множин точок у просторі будь-якої розмірності і для неевклідових метрик.
Пов'язані графи Граф відносних околsв є прикладом заснованого на бета-кістяка. Це підграф тріангуляції Делоне. У свою чергу, евклідове мінімальне кістякове дерево є його підграфом, звідки випливає, що це зв'язний граф.
Граф Уркгарта, утворений видаленням найдовшого ребра з кожного трикутника в тріангуляції Делоне, спочатку запропоновано як швидкий метод обчислення графа відносних околів. Хоча граф Уркхарта іноді відрізняється від графа відносних околів, його можна використати як апроксимацію графа відносних околів.
Примітки
Література