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

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

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

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

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

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

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

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

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

Тета-граф

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

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

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

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

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

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

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

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

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

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

Розширюваний вміст

Нам потрібні ці дві властивості ЦРДП: Лема 1: Нехай $\{A,B\}$ — цілком розділена декомпозиція пар відносно $s$. Нехай $p,p'\in A$ і $q\in B$. Тоді $|pp'|\leqslant (2/s)|pq|$. Лема 2: Нехай $\{A,B\}$ — цілком розділена декомпозиція пар відносно $s$. Нехай $p,p'\in A$ і $q,q'\in B$. Тоді, $|p'q'|\leqslant (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|\leqslant (2/s)|pq|\Rightarrow |pa|<|pq|$ і $|bq|\leqslant (2/s)|pq|\Rightarrow |bq|<|pq|$ за лемою 1 маємо: $|P_{pq}|\leqslant t|pa|+|ab|+t|bq|$ З леми 1 і 2 отримуємо: ${\begin{aligned}|P_{pq}|&\leqslant 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|\\&=\left({\frac {4(t+1)}{s}}+1\right)|pq|\end{aligned}}$ Так що: ${\begin{aligned}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{aligned}}$ Отже, якщо $t=(s+4)/(s-4)$ і $s>4$, то маємо $t$-кістяк для набору точок $S$.

Згідно з доведенням, можна мати довільне значення для $t$, виразивши $s$ із $t=(s+4)/(s-4)$, що дає $s=4(t+1)/(t-1)$.

Див. також

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

Література

• L. Paul Chew. There is a planar graph almost as good as the complete graph // Proc. 2nd Annual Symposium on Computational Geometry. — 1986. — DOI:10.1145/10515.10534.
• Rolf Klein, Martin Kutz. Computing Geometric Minimum-Dilation Graphs is NP-Hard // Proc. 14th International Symposium in Graph Drawing, Karlsruhe, Germany, 2006 / Michael Kaufmann, Dorothea Wagner. — Springer Verlag, 2007. — Т. 4372. — (Lecture Notes in Computer Science) — ISBN 978-3-540-70903-9. — DOI:10.1007/978-3-540-70904-6.
• Paul B. Callahan, S. Rao Kosaraju. Faster Algorithms for Some Geometric Graph Problems in Higher Dimensions // Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. — Austin, Texas, USA : Society for Industrial and Applied Mathematics, 1993. — (SODA '93) — ISBN 0-89871-313-7. — DOI:10.1145/313559.313777.
• Althöfer I., Das G., Dobkin D. P., Joseph D., Soares J. On sparse spanners of weighted graphs. // Discrete & Computational Geometry. — 1993. — Т. 9 (21 квітня). — DOI:10.1007/bf02189308.
• Bose P., Carmi P., Farshi M., Maheshwari A., Smid. M. Computing the greedy spanner in near-quadratic time // Algorithmica. — 2010. — Т. 58 (21 квітня). — DOI:10.1007/s00453-009-9293-4.
• Keil J. M., Gutwin C. A. Classes of graphs which approximate the complete Euclidean graph // Discrete and Computational Geometry. — 1992. — Т. 7, вип. 1 (21 квітня). — DOI:10.1007/BF02187821.
• Prosenjit Bose, Luc Devroye, Maarten Loeffler, Jack Snoeyink, Vishal Verma. The spanning ratio of the Delaunay triangulation is greater than $\scriptstyle {\pi /2}$ // Canadian Conference on Computational Geometry. — Vancouver, 2009.
• Callahan P. B., Kosaraju S. R. A Decomposition of Multidimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields // Journal of the ACM. — 1995. — Т. 42, вип. 1 (January). — DOI:10.1145/200836.200853.
• Giri Narasimhan, Michiel Smid. Geometric Spanner Networks. — Cambridge University Press, 2007. — ISBN 0-521-81513-4.