Граф відносних околів

Граф відносних околів 100 випадкових точок у одиничному квадраті.

Граф відно́сних о́колів — це неорієнтований граф, визначений на множині точок на евклідовій площині з'єднанням двох точок p і q ребом тоді, коли не існує третьої точки r, яка ближче як до p, так і до q, ніж p і q одна до одної. Цей граф 1980 року запропонував Годфрід Туссен^[en] як спосіб визначення на множині точок структури, яка відбиває людське сприйняття форми множини[1][2][3].

Алгоритми

Суповіт[4] показав, як ефективно побудувати граф відносних околів за час O(n log n)[5]. Граф можна обчислити за середній час O (n) для довільної множини точок, рівномірно розподілених у одиничному квадраті[6]. Граф відносних околів можна обчислити за лінійний час із тріангуляції Делоне множини точок[7][8].

Узагальнення

Оскільки граф визначений лише в термінах відстаней між точками, граф відносних околів можна визначити для множин точок у просторі будь-якої розмірності[1][9] і для неевклідових метрик[1][7][10][11].

Пов'язані графи

Граф відносних околsв є прикладом заснованого на лінзах^[en] бета-кістяка. Це підграф тріангуляції Делоне. У свою чергу, евклідове мінімальне кістякове дерево є його підграфом, звідки випливає, що це зв'язний граф.

Граф Уркгарта, утворений видаленням найдовшого ребра з кожного трикутника в тріангуляції Делоне, спочатку запропоновано як швидкий метод обчислення графа відносних околів[12]. Хоча граф Уркхарта іноді відрізняється від графа відносних околів[13], його можна використати як апроксимацію графа відносних околів[14].

Примітки

1. Jaromczyk, Kowaluk, 1991, с. 181–191.
2. Toussaint, 1980, с. 261–268.
3. Jaromczyk, Toussaint, 1992, с. 1502–1517.
4. Supowit, 1983.
5. Supowit, 1983, с. 428–448.
6. Katajainen, Nevalainen, Teuhola, 1987, с. 77–86.
7. Jaromczyk, Kowaluk, 1987, с. 233–241.
8. Lingas, 1994, с. 199–208.
9. Agarwal, Matoušek, 1992, с. 58–65.
10. O'Rourke, 1982, с. 189–192.
11. Lee, 1985, с. 327–332.
12. Urquhart, 1980, с. 556–557.
13. Toussaint, 1980, с. 860.
14. Andrade, de Figueiredo, 2001.

Література

• Toussaint G. T. The relative neighborhood graph of a finite planar set // Pattern Recognition. — 1980. — Т. 12, вип. 4. — С. 261–268. — DOI:10.1016/0031-3203(80)90066-7.
• Jaromczyk J.W., Toussaint G.T. Relative neighborhood graphs and their relatives // Proceedings of the IEEE. — 1992. — Т. 80, вип. 9. — С. 1502–1517. — DOI:10.1109/5.163414.
• Supowit K. J. The relative neighborhood graph, with an application to minimum spanning trees // J. ACM. — 1983. — Т. 30, вип. 3. — С. 428–448. — DOI:10.1145/2402.322386.
• Jyrki Katajainen, Olli Nevalainen, Jukka Teuhola. A linear expected-time algorithm for computing planar relative neighbourhood graphs // Information Processing Letters. — 1987. — Т. 25, вип. 2. — С. 77–86. — DOI:10.1016/0020-0190(87)90225-0.
• Jaromczyk J. W., Kowaluk M. A note on relative neighborhood graphs // Proc. 3rd Symp. Computational Geometry. — New York, NY, USA : ACM, 1987. — С. 233–241. — DOI:10.1145/41958.41983.
• Lingas A. A linear-time construction of the relative neighborhood graph from the Delaunay triangulation // Computational Geometry. — 1994. — Т. 4, вип. 4. — С. 199–208. — DOI:10.1016/0925-7721(94)90018-3.
• Jaromczyk J. W., Kowaluk M. Constructing the relative neighborhood graph in 3-dimensional Euclidean space // Discrete Appl. Math.. — 1991. — Т. 31, вип. 2. — С. 181–191. — DOI:10.1016/0166-218X(91)90069-9.
• Pankaj K. Agarwal, Jiří Matoušek. Relative neighborhood graphs in three dimensions // Proc. 3rd ACM–SIAM Symp. Discrete Algorithms. — 1992. — С. 58–65.
• O'Rourke J. Computing the relative neighborhood graph in the L₁ and L_∞ metrics // Pattern Recognition. — 1982. — Т. 15, вип. 3. — С. 189–192. — DOI:10.1016/0031-3203(82)90070-X.
• Lee D. T. Relative neighborhood graphs in the L₁-metric // Pattern Recognition. — 1985. — Т. 18, вип. 5. — С. 327–332. — DOI:10.1016/0031-3203(85)90023-8.
• Urquhart R. B. Algorithms for computation of relative neighborhood graph // Electronics Letters. — 1980. — Т. 16, вип. 14. — С. 556–557. — DOI:10.1049/el:19800386.
• Toussaint G. T. Comment: Algorithms for computing relative neighborhood graph // Electronics Letters. — 1980. — Т. 16, вип. 22. — С. 860. — DOI:10.1049/el:19800611.
• Diogo Vieira Andrade, Luiz Henrique de Figueiredo. Good approximations for the relative neighbourhood graph // Proc. 13th Canadian Conference on Computational Geometry. — 2001.