Проблема покрытия (передатчик и приемник)

Я пытаюсь решить следующую проблему покрытия.

Есть передатчиков с зоной покрытия 1 км и приемников. Определите в что все приемники охвачены любым передатчиком. Все приемники и передатчики представлены своими координатами и . $n$ $n$ $O(n\log n)$ $x$ $y$

Самое продвинутое решение, которое я могу найти, - . Для каждого приемника отсортируйте все передатчики по его расстоянию до этого текущего приемника, затем возьмите передатчик с самым коротким расстоянием, и это самое короткое расстояние должно быть в пределах 0,5 км. $O(n^2\log n)$

Но наивный подход выглядит намного лучше по временной сложности . Просто рассчитайте все расстояния между всеми парами передатчика и приемника. $O(n^2)$

Я не уверен, что смогу применить алгоритмы поиска диапазона в этой задаче. Например, kd-деревья позволяют нам находить такие диапазоны, однако я никогда не видел такого примера, и я не уверен, есть ли какой-то диапазон поиска кругов.

$O(n\log n)$

algorithms computational-geometry search-problem ком
источник

O (n \log n)

$O(n \log n)$

k d

$kd$

O (n \log n)

$O(n \log n)$

O (\log n)

$O(\log n)$

k d

$kd$

Я предполагаю, что алгоритм строчной линии может сделать свое дело: отсортировать и передатчики и приемники по x-координате и пройти по списку. Умное управление набором жизнеспособных передатчиков имеет важное значение.

Рафаэль

@ Рафаэль, не могли бы вы рассказать подробнее, похоже, в худшем случае это будет очень медленно.

ком

O (n \log n)

$O(n\log n)$

Ответы:

Для решения этой проблемы вы можете использовать диаграмму Вороного вместе со структурой данных Киркпатрика .

$\mathcal{O}(n \log n)$

$1\ \text{km}$

$\mathcal{O}(\log n)$ $\mathcal{O}(n\log n)$ $\mathcal{O}(n\log n)$

Каждая ячейка на диаграмме Вороного представляет собой выпуклый многоугольник, возможно, неограниченный.

...

Количество вершин [диаграммы Вороного из n узлов] V ≤ 2n-5

- www.cs.arizona.edu

$\Theta(v)$ $v$ $n$ $n$ $\mathcal{O}(n)$ $\mathcal{O}(n)$ $\mathcal{O}(n)$ $\mathcal{O}(n)$ $\mathcal{O}(n)$

Реал Слав
источник