Как реализовать поиск точки с минимальной плотностью в ограниченном плоском пространстве?
Как алгоритмически правильно решить задачу на поиск точки с минимальной плотностью (поиск самой разреженной точки)?
Искомая точка не содержится в наборе — её координаты нужно вычислить, "обнаружить".
Например для пространства [(0; 0); (1; 1)] содержащего нижеприведённые точки A₁, B₁, C₁ и D₁, искомой новой точкой является E₁ (0,5; 0,5):
То есть под искомой точкой E я подразумеваю такую точку в заданном пространстве, которая находилось бы на максимальном возможном расстоянии от всех остальных точек в нём. Иначе говоря такую, чтобы расстояние от неё до другой ближайшей точки в пространстве было максимальным.
Ответы (2 шт):
Строим диаграмму Вороного за O(n log n).
Кроме того, строим выпуклую оболочку точек.
Теперь возможные центры наибольшей пустой окружности - это узлы диаграммы, лежащие внутри оболочки, а также пересечения ребер диаграммы с выпуклой оболочкой. Из этих центров выбирается тот, что обеспечивает наибольший радиус (это может оказаться не так просто, но для небольшого количества точек проще проверить все расстояния от центров-кандидатов)
Дан центр q. Окружность Cq называется пустой если никакие точки множества S не лежат внутри окружности. Максимальная пустая окружность - тоже самое с максимальным радиусом. Очевидно что радиус максимальной пустой окружности - непрерывная функция от q. Она ограничена, если точке q запрещено покидать некоторую компактную область (прямоугольник). Тогда она достигает своего максимума на этом компакте.
В дальнейшем Cq обозначает только максимальную пустую окружность.
Пересечение Cq c S не пусто - следствие максимальности.
Если в пересечении ровно одна точка p и q внутри области, то можно "отодвинуть" q от p и получить q', такую что радиус Cq' будет больше радиуса Cq.
Если в пересечении ровно две точки p1 и p2 и q внутри области, то можно "отодвинуть" q вдоль срединного перепендикуляра к отрезку p1p2 и получить q', такую что радиус Cq' будет больше радиуса Cq.
Если в пересечении ровно одна точка p и q внутри ребра области (то есть на границе но не в углу), её можно сдвинуть вдоль границы и получить больший радиус.
Отброшены три случая. Остались
точка q внутри области, на границе Cq три или больше точек S;
точка q внутри ребра области, на границе Cq две или больше точек S;
точка q в углу области.
Первая категория - вершины диаграммы Вороного. Вторая категория - пересечения рёбер диаграммы Вороного с границей области. Третья категория - вершины границы области. Все категории перебираются за линейное время, если вы умеете строить диаграмму Вороного.
Без построения диаграммы есть алгоритм за N4. Перебираете все тройки точек, по тройке строите окружность, проверяете её пустоту (время N4). Перебираете все пары точек, строите срединные перепендикуляры, пересекаете их с границей области, в пересечениях строите окружности, проверяете их пустоту (время KN2, K - число углов области). Во всех углах области строите максимальные пустые окружности (время NK, K - число углов области).