Найти все пары отрезков с расстоянием меньше определенной границы

Question

Пусть L1, ..., Ln - n различных отрезков на плоскости (IR ^ 2). Они должны быть попарно не пересекающимися. Кроме того, пусть r означает расстояние (реальное значение). Рассмотрим проблему нахождения всех пар (i, j), в которых (евклидово) расстояние Li и Lj меньше r.

Я написал простой и прямой алгоритм строчной линии для задачи, которая о время выполнения O (n ^ (3/2)), если можно предположить, что для всех соответствующих координат x0 около n ^ (1/2) отрезков линии l ie в вертикальной полосе, ограниченной x = x0 и x = x0 + r.

Конечно, мне было любопытно, если есть хорошо известный (или не очень известный) лучший алгоритм (возможно, алгоритм O (n log (n)) или тому подобное), но не смог найди что нибудь подходящее через гугл или точнее stackoverflow.

Кто-нибудь знает больше?

Answer 1

Если вы замените сегменты прямоугольниками, соответствующими расширению на r/2, контуры прямоугольника будут пересекаться, когда сегменты ближе, чем r. (На самом деле, будет несколько ложных срабатываний, потому что углы должны быть закруглены. Но ложные срабатывания могут быть отклонены после факта.)

Таким образом, вы можете использовать стандартный Bentley-Ottman для выполнения ваших задание, без ухудшения асимптотики c сложность. (Обратите внимание, что два контура прямоугольника могут пересекаться до восьми раз, но только в экстремальных ситуациях.)

https://en.wikipedia.org/wiki/Bentley –Ottmann_algorithm