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

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

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

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

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

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

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

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

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

Тета-граф

Докладніше: Тета-граф

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

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

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

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

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

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

Докладніше: Тріангуляція Делоне

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

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

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

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

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

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

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

Див. також

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

Примітки

1. Narasimhan, Smid, 2007.
2. Chew, 1986, с. 169–177.
3. Klein, Kutz, 2007, с. 196–207.
4. Althöfer, Das, Dobkin, Joseph, Soares, 1993, с. 81–100.
5. Bose, Carmi, Farshi, Maheshwari, Smid, 2010, с. 711–729.
6. Keil, Gutwin, 1992, с. 13–28.
7. Bose, Devroye, Loeffler, Snoeyink, Verma, 2009, с. 165–167.
8. Callahan, Kosaraju, 1995, с. 67–90.

Література

• 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. — () — . — 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) — . — 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 (18 червня). — 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 (18 червня). — DOI:10.1007/s00453-009-9293-4.
• Keil J. M., Gutwin C. A. Classes of graphs which approximate the complete Euclidean graph // . — 1992. — Т. 7, вип. 1 (18 червня). — DOI:10.1007/BF02187821.
• Prosenjit Bose, Luc Devroye, Maarten Loeffler, Jack Snoeyink, Vishal Verma. The spanning ratio of the Delaunay triangulation is greater than ${\displaystyle \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. — .