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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Граф відносних околів 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 L1 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 L1-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.
Отримано з https://uk.wikipedia.org/w/index.php?title=Граф_відносних_околів&oldid=41657208