Граф относительных окрестностей

Граф относительных окрестностей — это неориентированный граф, определённый на множестве точек на евклидовой плоскости путём соединения двух точек p и q ребром, когда не существует третьей точки r, которая ближе как к p, так и q, чем p и q друг к другу. Этот граф предложил Годфрид Туссен в 1980 как способ определения структуры на множестве точек, которая отражает человеческое восприятие формы множества[1][2][3].

Граф относительных окрестностей 100 случайных точек в единичном квадрате.

Алгоритмы

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

Обобщения

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

Связанные графы

Граф относительных окрестностей является примером основанного на линзах бета-остова. Это подграф триангуляции Делоне. В свою очередь, евклидово минимальное остовное дерево является его подграфом, откуда следует, что это связный граф.

Граф Уркхарта, образованный удалением наиболее длинного ребра из каждого треугольника в триангуляции Делоне, был первоначально предложен как быстрый метод вычисления графа относительных окрестностей[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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.