Оптимизация алгоритма конверта - лучшее место для круга

Question

Мне нужно оптимально решить следующую проблему.

Входные данные:

• N точек на плоскости, заданной как (x, y) пара целочисленных координат
• M точек в той же плоскости, заданных как (x, y) пара целочисленных координат, представляющих центр круга. Все эти круги имеют (0, 0) на своих краях.

Мне нужно найти способ выделить несколько кругов, обладающих свойством, чем для любого «хорошего» круга, ни одна точка из первых N точек не лежит в выбранном круге или на краю выбранного круга.

Количество точек и кружков составляет порядка 100 000. Очевидное решение проверки каждого круга с каждой точкой имеет сложность O (N * M), и при 100 000 кругов и 100 000 точек на Core 2 Duo с 64-битным кодом SSE3 одинарной точности требуется около 15 секунд. Эталонная реализация, с которой я конкурирую, занимает всего около 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 </li>

(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 0
• Yc> MAX (E (Xc)) (5.2) для всех точек с y <0 </li>

Мы можем видеть, что E (Xc) является линейной функцией относительно Xc с 2 параметрами - A (x, y) и B (x, y). Это означает, что в основном E (Xc) представляет в евклидовом пространстве семейство линий с 2 ​​параметрами.

Теперь вот часть, которую я не понимаю. Они говорят, что из-за свойства, указанного в предыдущем параграфе, мы можем вычислить MIN () и MAX () в O (1) амортизированном времени вместо O (N), используя алгоритм Envelope. Я не знаю, как может работать алгоритм конвертов.

Любые советы о том, как реализовать алгоритм Envelope?

Заранее спасибо!

---

Edit:

Вопрос не в том, что такое конверт в математическом смысле - я это уже знаю. Вопрос состоит в том, как определить огибающую за лучшее время, чем O (n), по-видимому, это можно сделать в амортизированной форме O (1).

У меня есть семейство функций, мне нужно вычислить огибающую, и у меня есть массив всех возможных параметров. Как оптимально решить задачу максимизации?

Еще раз спасибо!

Answer 1

Я думаю, что вы можете сделать это с помощью диаграммы Вороного:

• Создание диаграммы Вороного из {N points} union {[0,0]}
• Центры окружностей, не соприкасающиеся с N точками, как раз и находятся внутри ячейки Вороного точки [0,0], которая является выпуклым многоугольником
• Отфильтруйте M точек, один тест должен принять O (log C) = O (log N) [где C - количество вершин в ячейке [0,0]

Общая сложность должна быть O (N log N + M log N)

Answer 2

• Создайте R-Tree из всех точек в первом наборе.
• Для каждой точки во втором наборе вычислите ограничивающую рамку его окружности и найдите все точки в R-дереве, которые попадают в эту ограничивающую рамку (O (n log n) относительно числа возвращенных точек) .
• Проверьте расстояние между каждой возвращаемой точкой и точкой, которая в данный момент рассматривается; откажитесь от всего, что находится внутри ограничительной рамки, но за пределами круга.

Answer 3

У меня нет математического фона, но я бы подошел к этой проблеме в три этапа:

• Отбросьте большинство точек в N. Это сложная часть. Каждая пара точек «затеняет» область «позади», если смотреть с начала координат. Эта область ограничена двумя лучами, начинающимися от точек наружу, указывающими на начало координат, и круговым пересечением между точками. Расчет этого может быть намного проще в полярных координатах. Начните со случайной пары, затем посмотрите на одну новую точку за раз: если она затенена, выбросьте ее; если нет, выясните, затеняет ли он какую-либо точку в вашем наборе, а затем восстановите огибающий набор кривых. Тесты для восстановления части огибающей кривой должны занимать почти постоянное время, потому что набор теней вряд ли будет расти за определенное небольшое число. Наихудший случай для этого, кажется, O (NlogN). Я не могу представить, что какое-либо решение может быть лучше, чем O (N), потому что вы должны смотреть на каждую точку в любом случае.

• Выбросить большинство точек в M. Это довольно просто: если точка от M находится дальше от начала координат, чем на половину расстояния до самой дальней точки от набора огибающих, то ее можно выбросить. Это занимает O (M)

• Отфильтруйте оставшиеся точки в М через фактическую проверку. Сколько времени это займет, зависит от распределения N и M, но я думаю, что почти O (1), если оба числа большие, а распределения аналогичные.

В целом, это возможно в O (N log (N) + M). Хотя никаких гарантий;)

Answer 4

Вот запись Википедии на конвертах . Вот урок о теореме об огибающей в оптимизации .

Answer 5

Никогда не принимайте sqrt. Оставьте все расстояния как их квадраты. При этом вы можете сравнить их, но время в 2-3 раза меньше.

Answer 6

Рассмотрим некоторые другие аспекты ваших вычислений.

Например, вы, очевидно, сравниваете много расстояний. Каждый принимает вызов в SQRT. Почему бы не сравнить «квадраты расстояний»? SQRT является дорогостоящим вычислением.