У меня есть множество P из n точек в 2-мерном пространстве. Я должен выполнить следующий запрос по этим точкам:
Учитывая набор X, который является подмножеством P, найти точку в множестве P \ X, которая имеет максимальное расстояние до всех точек в X Другими словами, найдите точку y в P \ X, которая максимизирует расстояние между y и любой точкой в X.
Я должен выполнить запрос много раз. Я могу выполнить запрос за O (n ^ 2) времени, проверив все попарные расстояния. Я ищу структуру данных, которая дает вывод запроса в логарифмическом c времени. Кроме того, я хочу построить структуру данных менее чем за O (n ^ 2) времени.
NB: Для любого набора P из n точек, используя расположение точки в самой дальней точке диаграммы Вороного из P, для любой точки q мы можем найти ее самую дальнюю точку в P за логарифмическое время c. ( см. Этот вопрос )