Манхэттенский алгоритм дистанционного собеседования

Question

Учитывая набор n точек в плоскости XY, как я могу определить, отделена ли каждая точка, по крайней мере, от любой другой точки на расстоянии в 5 единиц на Манхэттене во времени меньше, чем O (n ^ 2)

Каков наилучший алгоритм для реализации этого?

Спасибо.

Answer 1

1. Сортировка точек по x. Это занимает время 'O (n log (n))'.

2. Разделите диапазон на полосы шириной 10. (Здесь вам понадобится очевидная осторожность для патологического случая, когда одна точка имеет x-координату 1, а другая - x-координату 10 ^20. .) O(n)

3. Для каждой полосы:

   1. Возьмите набор точек в пределах этой полосы или в пределах x от 5 по обе стороны и отсортируйте их по y. Это O(n log(n)) по всем полосам.
   2. Для каждой точки в полосе найдите расстояние Манхэттена до всех остальных точек в этой чуть более широкой полосе, координата которой у находится в пределах 5 от их собственной. Если вы найдете что-либо на расстоянии 5, выйдите и сообщите ложь. Это O(n) для всех полос.

4. Сообщить правду.

Этот алгоритм O(n log(n)). Я настоятельно советую вам продемонстрировать для себя, что поточечное сравнение Манхэттена в 1.2 требует O(n) операций, даже , если ответ ложный.

Для истины это просто - это следует из того факта, что существует максимальное количество других точек, которые можно сжать в коробке 20х10 без 2-х попаданий в 5. Для ложа это сложнее, вы можете иметь много других точек в этом поле, но к тому времени, когда вы сравнили фиксированное количество их с остальными, вы должны были найти два на расстоянии 5. В любом случае данная точка участвует в фиксированном максимальном количестве сравнений между точками до того, как вы получите ответить.