Граф относительных окрестностей — это неориентированный граф, определённый на множестве точек на евклидовой плоскости путём соединения двух точек p и q ребром, когда не существует третьей точки r, которая ближе как к p, так и q, чем p и q друг к другу. Этот граф предложил Годфрид Туссен в 1980 как способ определения структуры на множестве точек, которая отражает человеческое восприятие формы множества.
Алгоритмы Суповит показал, как эффективно построить граф относительных окрестностей за время O(n log n). Граф можно вычислить за среднее время O (n) для произвольного множества точек равномерно распределённых в единичном квадрате. Граф относительных окрестностей можно вычислить за линейное время из триангуляции Делоне множества точек.
Обобщения Поскольку граф определён лишь в терминах расстояний между точками, граф относительных окрестностей может быть определён для множеств точек в пространстве любой размерности и для неевклидовых метрик.
Связанные графы Граф относительных окрестностей является примером основанного на бета-остова. Это подграф триангуляции Делоне. В свою очередь, евклидово минимальное остовное дерево является его подграфом, откуда следует, что это связный граф.
Граф Уркхарта, образованный удалением наиболее длинного ребра из каждого треугольника в триангуляции Делоне, был первоначально предложен как быстрый метод вычисления графа относительных окрестностей. Хотя граф Уркхарта иногда отличается от графа относительных окрестностей , он может быть использован в качестве аппроксимации графу относительных окрестностей.
Примечания
Литература
Категория:Геометрические графы