Геометричний кістяк

Геометричний кістяк (Шаблон:Lang-en) або t-кістяковий граф, або t-кістяк спочатку введено як зважений граф на множині точок як вершин, для якого існує t-шлях між будь-якою парою вершин для фіксованого параметра t. t-шлях визначають як шлях у графі з вагою, що не перевищує в t разів просторову відстань між кінцевими точками. Параметр t називають Шаблон:Не перекладено кістякаШаблон:Sfn.

В обчислювальній геометрії концепцію першим обговорював Л. П. Чу (1986)Шаблон:Sfn, хоча термін «spanner» (кістяк) у статті не згадано.

Поняття кістякового дерева відоме в теорії графів: t-кістяки — це кістякові підграфи графів зі схожими властивостями розтягування, де відстань між вершинами графа визначається в термінах теорії графів. Тому геометричні кістяки є кістяковими деревами повних графів, укладених у площину, в яких ваги ребер дорівнюють відстаням між вершинами у відповідній метриці.

Остовы можна використати в обчислювальній геометрії для розв'язання деяких Шаблон:Не перекладено. Вони мають також застосування в інших галузях, таких як планування руху, в комунікаційних мережах — надійність мережі, оптимізація роумінгу в мобільних мережах тощо.

Різні кістяки та міри якості

Для аналізу якості кістяків використовують різні міри. Найпоширенішими мірами є число ребер, загальна вага та найбільший степінь вершин. Асимптотично оптимальні значення для цих мір — $O(n)$ ребер, $O(MST)$ для загальної ваги та $O(1)$ для найбільшого степеня (тут MST означає вагу мінімального кістякового дерева).

Відомо, що пошук кістяка на евклідовій площині з найменшим розтягом на n точках з максимум m ребрами є NP-складною задачеюШаблон:Sfn.

Є багато алгоритмів, які добре поводяться за різних мір якості. Швидкі алгоритми включають кістякову Шаблон:Не перекладено (ЦРДП) і тета-графи, які будують кістяки з лінійним числом ребер за час $O(n\log n)$. Якщо потрібні кращі ваги і степені вершин, жадібний кістяк обчислюється майже за квадратичний час.

Тета-граф

Шаблон:Докладніше Тета-граф або $\mathrm{\Theta }$ -граф належить до сімейства кістяків, заснованих на конусі. Основний метод побудови полягає в поділі простору навколо кожної вершини на множину конусів (плоский конус - це два промені, тобто кут), які поділяють вершини графа, що залишилися. Подібно до графів Яо, $\mathrm{\Theta }$-граф містить максимум по одному ребру для конуса. Підхід відрізняється способом вибору ребер. Тоді як у графах Яо вибирають найближчу вершину відповідно до метричної відстані у графі, у $\mathrm{\Theta }$-графі визначають фіксований промінь, що міститься в кожному конусі (зазвичай бісектрису конуса) і вибирають найближчих сусідів (тобто з найменшою відстанню до променя).

Жадібний кістяк

Жадібний кістяк або жадібний граф визначають як граф, отриманий багаторазовим додаванням ребра між точками, що не мають t-шляху. Алгоритми обчислення цього графа згадують як алгоритми жадібного кістяка. З побудови очевидно випливає, що жадібні графи є t-кістяками.

Жадібні кістяки відкрили 1989 року незалежно АльтхеферШаблон:Sfn і Берн (не опубліковано).

Жадібний кістяк досягає асимптотично оптимального числа ребер, загальної ваги і найбільшого степеня вершини і дає кращі величини міри на практиці. Його можна побудувати за час $O(n^2\log n)$ з використанням простору $O(n^2)$Шаблон:Sfn.

Тріангуляція Делоне

Шаблон:Докладніше Головним результатом Чу було те, що для множини точок на площині існує тріангуляція цих наборів точок, така, що для будь-яких двох точок існує шлях уздовж ребер тріангуляції з довжиною, що не перевищує $\sqrt{1}0$ евклідової відстані між двома точками. Результат використано в плануванні руху для пошуку прийнятного наближення найкоротшого шляху серед перешкод.

Найкраща верхня відома межа для тріангуляції Делоне дорівнює $(4\sqrt{3}/9)\pi \approx 2,418$-кістяка для його вершинШаблон:Sfn. Нижню межу збільшено від $\pi /2$ до 1,5846Шаблон:Sfn.

Цілком розділена декомпозиція пар

Кістяк можна побудувати з Шаблон:Не перекладено у такий спосіб. Будуємо граф із набором точок $S$ як вершинами і для кожної пари $\{A,B\}$ в ЦРДП додаємо ребро з довільної точки $a\in A$ до довільної точки $b\in B$. Зауважимо, що отриманий граф має лінійне число ребер, оскільки ЦРДП має лінійне число парШаблон:Sfn.Шаблон:Collapse top Нам потрібні ці дві Шаблон:Не перекладено:

Лема 1: Нехай $\{A,B\}$ — цілком розділена декомпозиція пар відносно $s$. Нехай $p,p^{\prime }\in A$ і $q\in B$. Тоді $|p{p}^{\prime }|⩽(2/s)|pq|$.

Лема 2: Нехай $\{A,B\}$ — цілком розділена декомпозиція пар відносно $s$. Нехай $p,p^{\prime }\in A$ і $q,q^{\prime }\in B$. Тоді, $|p^{\prime }{q}^{\prime }|⩽(1+4/s)|pq|$.

Нехай $\{A,B\}$ — цілком розділена декомпозиція пар відносно $s$. Нехай $[a,b]$ — ребро, що з'єднує $A$ з $B$. Нехай є точка $p\in A$ і точка $q\in B$. За визначенням ЦРДП достатньо перевірити, що є $t$-кістяковий шлях, або, коротше, $t$-шлях, між $p$ і $q$, який позначимо $P_{pq}$. Позначимо довжину шляху $P_{pq}$ через $|P_{pq}|$.

Припустимо, що є $t$-шлях між будь-якою парою точок із відстанню, меншою або рівною $|pq|$ і $s>2$. З нерівності трикутника, припущень і факту, що $|pa|⩽(2/s)|pq|\Rightarrow |pa|<|pq|$ і $|bq|⩽(2/s)|pq|\Rightarrow |bq|<|pq|$ за лемою 1 маємо:

$|P_{pq}|⩽t|pa|+|ab|+t|bq|$

З леми 1 і 2 отримуємо:

$\begin{array}{cc}|P_{pq}|& ⩽t(2/s)|pq|+(1+4/s)|pq|+t(2/s)|pq|\\ & =t(4/s)|pq|+(1+4/s)|pq|\\ & =\left(\frac{4t+4}{s}\right)|pq|+|pq|\\ & =(\frac{4(t+1)}{s}+1)|pq|\end{array}$

Так що:

$\begin{array}{cc}t& =\frac{4(t+1)}{s}+1\\ t-1& =\frac{4(t+1)}{s}\\ s(t-1)& =4(t+1)\\ s(t-1)-4(t+1)& =0\\ st-s-4t-4& =0\\ t(s-4)-s-4& =0\\ t(s-4)& =s+4\\ t& =\frac{s+4}{s-4}\end{array}$

Отже, якщо $t=(s+4)/(s-4)$ і $s>4$, то маємо $t$-кістяк для набору точок $S$. Шаблон:Collapse bottomЗгідно з доведенням, можна мати довільне значення для $t$, виразивши $s$ із $t=(s+4)/(s-4)$, що дає $s=4(t+1)/(t-1)$.

Див. також

• Деревний кістяк
• Евклідове мінімальне кістякове дерево

Література

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Книга