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

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

Алгоритмы

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

Обобщения

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

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

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

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

Примечания

↑ ¹ ² ³ Jaromczyk, Kowaluk, 1991, с. 181–191.
↑ Toussaint, 1980, с. 261–268.
↑ Jaromczyk, Toussaint, 1992, с. 1502–1517.
↑ Supowit, 1983.
↑ Supowit, 1983, с. 428–448.
↑ Katajainen, Nevalainen, Teuhola, 1987, с. 77–86.
↑ ¹ ² Jaromczyk, Kowaluk, 1987, с. 233–241.
↑ Lingas, 1994, с. 199–208.
↑ Agarwal, Matoušek, 1992, с. 58–65.
↑ O'Rourke, 1982, с. 189–192.
↑ Lee, 1985, с. 327–332.
↑ Urquhart, 1980, с. 556–557.
↑ Toussaint, 1980, с. 860.
↑ 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.