Мне нужно решить следующую задачу оптимальным образом.
Входные данные:
- N точек на плоскости, заданной как (x, y) пара целочисленных координат
- M точек на той же плоскости, заданной как пара целых чисел (x, y), представляющих центр окружности. Все эти круги имеют (0, 0) на краю.
Мне нужно найти способ выделения ряда окружностей, обладающих тем свойством, что для любой «хорошей» окружности ни одна точка из первых N точек не лежит в выбранной окружности или на краю выбранной окружности.
Количество точек и кругов порядка 100 000. Очевидное решение проверки каждого круга с каждой точкой имеет сложность O(N * M), а при 100 000 кругов и 100 000 точек это занимает около 15 секунд на Core 2 Duo с 64-битным кодом одинарной точности SSE3. Эталонная реализация, с которой я конкурирую, занимает всего около 0,1 секунды с теми же данными. Я знаю, что эталонная реализация - O (Nlog N + Mlog M).
Я подумал об оптимизации своего алгоритма следующим образом. Сделайте 2 копии точечных данных и отсортируйте копии по координате x и соответственно по координате y. Затем используйте только точки, лежащие в квадрате, определяемом [(xc - r, yc - r); (xc + r, yc + r)], где (xc, yc) — центр «текущей» окружности радиусом r. Я могу найти точки в этом интервале с помощью бинарного поиска, потому что теперь я работаю с отсортированными данными. Сложность этого подхода должна быть O(Nlog N + Mlog^2 N), и он действительно быстрее, но все же значительно медленнее, чем эталонный.
Я более или менее знаю, как работает эталонная реализация, но есть некоторые шаги, которые я не понимаю. Я попытаюсь объяснить то, что я знаю до сих пор:
Радиус окружности с координатами (Xc, Yc):
- Rc = sqrt(Xc * Xc + Yc * Yc) (1)
Это потому, что (0, 0) находится на краю круга.
Чтобы точка P(x, y) находилась вне круга, должно выполняться следующее неравенство:
- sqrt((Xc - x)^2 + (Yc - y)^2) > Rc (2)
Теперь, если мы подставим Rc из (1) в (2), то возведем в квадрат неравенство, после простых вычислений получим:
- Yc ‹ 1/2y * (x^2 + y^2) - Xc * x/y (3.1) для y > 0
- Yc > 1/2y * (x^2 + y^2) - Xc * x/y (3.2) при y ‹ 0
(3.1) и (3.2) должны выполняться для данной окружности C(Xc, Yc) при любых (x, y), выбранных из входных данных.
Для простоты сделаем несколько обозначений:
- A(x, y) = 1/2y * (x^2 + y^2) (4.1)
- B(x, y) = -x/y (4.2)
- E(Xc) = 1/2y * (x^2 + y^2) - Xc * x/y = A(x, y) + Xc * B(x, y) (4.3)
Мы можем видеть, что для данной окружности C(Xc, Yc) мы можем записать (3) как:
- Yc ‹ MIN(E(Xc)) (5.1) для всех точек с y > 0
- Yc > MAX(E(Xc)) (5.2) для всех точек с y ‹ 0
Мы можем видеть, что E(Xc) — линейная функция относительно Xc с двумя параметрами — A(x, y) и B(x, y). Это означает, что в основном E(Xc) представляет в евклидовом пространстве семейство прямых с двумя параметрами.
Теперь вот часть, которую я не понимаю. Они говорят, что из-за свойства, указанного в предыдущем абзаце, мы можем вычислить MIN() и MAX() за O(1) амортизированного времени вместо O(N) времени, используя алгоритм Envelope. Я не знаю, как может работать алгоритм Envelope.
Любые подсказки о том, как реализовать алгоритм Envelope?
Заранее спасибо!
Изменить:
Вопрос не в том, что такое оболочка в математическом смысле — это я и так знаю. Вопрос в том, как определить конверт за время, лучшее, чем O(n), по-видимому, это можно сделать за амортизированное время O(1).
У меня есть семейство функций, которое мне нужно для вычисления конверта, и у меня есть массив всех возможных параметров. Как решить задачу максимизации оптимальным образом?
Еще раз спасибо!
