Поиск двух ближайших точек: различия между версиями
| Строка 2: | Строка 2: | ||
Даны $n$ точек на плоскости, необходимо найти $2$ из них, расстояние между которыми минимально. | Даны $n$ точек на плоскости, необходимо найти $2$ из них, расстояние между которыми минимально. | ||
| − | == | + | == Обозначения == |
$P_{(i)}$ означает $i$-ую точку множества $P$, отсортированного по $x$-координате. | $P_{(i)}$ означает $i$-ую точку множества $P$, отсортированного по $x$-координате. | ||
| + | $p^(y)$ означает $y$-координату точки $p$. | ||
| − | = | + | = Идеи решения = |
Воспользуемся идеей <<Разделяй-и-властвуй>>: разобьём наше множество по $x$-координате точек на два: $P_1$ и $P_2$ $|P_{i}| = \frac{n}{2}$ в каждом, рекурсивно найдём ответ в каждом из них: $d_1$ и $d_2$, а после этого попытаемся найти пару точек $p_1 \in P_1$ и $p_2 \in P_2$ таких что $\rho(p_1, p_2) < min(d_1, d_2) = d$. | Воспользуемся идеей <<Разделяй-и-властвуй>>: разобьём наше множество по $x$-координате точек на два: $P_1$ и $P_2$ $|P_{i}| = \frac{n}{2}$ в каждом, рекурсивно найдём ответ в каждом из них: $d_1$ и $d_2$, а после этого попытаемся найти пару точек $p_1 \in P_1$ и $p_2 \in P_2$ таких что $\rho(p_1, p_2) < min(d_1, d_2) = d$. | ||
| − | Будем перебирать только те пары точек из обоих множеств, которые потенциально могут дать результат, лучше чем $d$. Заметим, что это означает, что нет смысла рассматривать точки, чья $x$-координата отличается от $x$-координаты $P_{(n | + | Будем перебирать только те пары точек из обоих множеств, которые потенциально могут дать результат, лучше чем $d$. Заметим, что это означает, что нет смысла рассматривать точки, чья $x$-координата отличается от $x$-координаты $P_{(\frac{n}{2})}$ хотя бы на $d$. Более того, зафиксировав, скажем $p_1 \in P_1$, нет смысла рассматривать с ней в паре точки $p_2 \in P_2$, которые отличаются по $y$-координате также хотя бы на $d$. |
| − | Таким образом, для каждой точки из $P_1$ имеет смысл | + | Таким образом, для каждой точки из $P_1$ имеет смысл рассматривать только те точки из $P_2$, которые лежат в прямоугольнике размера $d \times 2d$. В дальнейшем мы докажем, что количество таких точек не превосходит некоторой константы, из чего следует, что число потенциально улучшающих ответ пар (на шаге слияния) не более чем линейно по $n$. |
| + | |||
| + | = Детали реализации = | ||
| + | |||
| + | == Предварительная сортировка по $x$-координате == | ||
| + | |||
| + | Заметим, что на каждом шаге рекурсии мы разделяем текущее множество точек по $x$-координате его медианы. Чтобы не сортировать каждый раз, отсортируем все точки вначале и будем передавать в рекурсию индексы множества точек, с которым мы сейчас работаем. | ||
| + | |||
| + | == Внутренняя сортировка по $y$-координате == | ||
| + | |||
| + | Чтобы перебирать только те пары точек, которые нам интересны, хочется иметь точки внутри обеих полос шириной $d$ (по обе стороны от $P_{(\frac{n}{2})}) отсортированными по $y$. Для этого можно потребовать, чтобы рекурсивный вызов не только возвращал ответ $d_i, i \in \{ 1, 2 \}$ в подзадаче, но и два (отсортированных по $y$-координате)списка точек, которые находятся на расстоянии $d_i$ от границ множества, на котором мы вызываемся (списка 2, потому что границ тоже 2). | ||
| + | |||
| + | Тогда на стадии слияния нам нужно будет рассмотреть 2 из 4 полученных из рекурсии полос (те, которые находятся по бокам от разделяющей линии), а наверх передать те точки из оставшихся (боковых) полос, которые отстоят от границ не дальше, чем ответ, полученный после объединения (ведь мы вполне могли найти расстояние меньшее, чем полученное в рекурсивных вызовах). | ||
| + | |||
| + | == 2 указателя == | ||
| + | |||
| + | Теперь, имея 2 списка точек в средних полосах, отсортированных по $y$-координате, нам достаточно пройтись 2 указателями, так чтобы расстояние между точками, на которые смотрят указатели, не превышало $min(d_1, d_2)=d$. Заметим, что для каждой новой точки в $P_1$ (назовём её, внезапно, $p_1$) нам необязательно каждый раз просматривать все точки $P_2$ заново, достаточно откатить второй указатель наз до тех пор, пока он не начнёт указывать на точку из $P_2$, $y$-координата которой меньше (мы считаем, что оба указателя идут по полосам снизу-вверх) $p_1^(y) - d$ (либо пока указатель не упрётся в начало списка). | ||
Версия 19:28, 2 марта 2020
Содержание
Задача
Даны $n$ точек на плоскости, необходимо найти $2$ из них, расстояние между которыми минимально.
Обозначения
$P_{(i)}$ означает $i$-ую точку множества $P$, отсортированного по $x$-координате. $p^(y)$ означает $y$-координату точки $p$.
Идеи решения
Воспользуемся идеей <<Разделяй-и-властвуй>>: разобьём наше множество по $x$-координате точек на два: $P_1$ и $P_2$ $|P_{i}| = \frac{n}{2}$ в каждом, рекурсивно найдём ответ в каждом из них: $d_1$ и $d_2$, а после этого попытаемся найти пару точек $p_1 \in P_1$ и $p_2 \in P_2$ таких что $\rho(p_1, p_2) < min(d_1, d_2) = d$.
Будем перебирать только те пары точек из обоих множеств, которые потенциально могут дать результат, лучше чем $d$. Заметим, что это означает, что нет смысла рассматривать точки, чья $x$-координата отличается от $x$-координаты $P_{(\frac{n}{2})}$ хотя бы на $d$. Более того, зафиксировав, скажем $p_1 \in P_1$, нет смысла рассматривать с ней в паре точки $p_2 \in P_2$, которые отличаются по $y$-координате также хотя бы на $d$.
Таким образом, для каждой точки из $P_1$ имеет смысл рассматривать только те точки из $P_2$, которые лежат в прямоугольнике размера $d \times 2d$. В дальнейшем мы докажем, что количество таких точек не превосходит некоторой константы, из чего следует, что число потенциально улучшающих ответ пар (на шаге слияния) не более чем линейно по $n$.
Детали реализации
Предварительная сортировка по $x$-координате
Заметим, что на каждом шаге рекурсии мы разделяем текущее множество точек по $x$-координате его медианы. Чтобы не сортировать каждый раз, отсортируем все точки вначале и будем передавать в рекурсию индексы множества точек, с которым мы сейчас работаем.
Внутренняя сортировка по $y$-координате
Чтобы перебирать только те пары точек, которые нам интересны, хочется иметь точки внутри обеих полос шириной $d$ (по обе стороны от $P_{(\frac{n}{2})}) отсортированными по $y$. Для этого можно потребовать, чтобы рекурсивный вызов не только возвращал ответ $d_i, i \in \{ 1, 2 \}$ в подзадаче, но и два (отсортированных по $y$-координате)списка точек, которые находятся на расстоянии $d_i$ от границ множества, на котором мы вызываемся (списка 2, потому что границ тоже 2). Тогда на стадии слияния нам нужно будет рассмотреть 2 из 4 полученных из рекурсии полос (те, которые находятся по бокам от разделяющей линии), а наверх передать те точки из оставшихся (боковых) полос, которые отстоят от границ не дальше, чем ответ, полученный после объединения (ведь мы вполне могли найти расстояние меньшее, чем полученное в рекурсивных вызовах). =='"`UNIQ--h-6--QINU`"' 2 указателя == Теперь, имея 2 списка точек в средних полосах, отсортированных по $y$-координате, нам достаточно пройтись 2 указателями, так чтобы расстояние между точками, на которые смотрят указатели, не превышало $min(d_1, d_2)=d$. Заметим, что для каждой новой точки в $P_1$ (назовём её, внезапно, $p_1$) нам необязательно каждый раз просматривать все точки $P_2$ заново, достаточно откатить второй указатель наз до тех пор, пока он не начнёт указывать на точку из $P_2$, $y$-координата которой меньше (мы считаем, что оба указателя идут по полосам снизу-вверх) $p_1^(y) - d$ (либо пока указатель не упрётся в начало списка).