Бихроматическая ближайшая пара, когда R и B разделены вертикальной линией (продолжение) - PullRequest
Новая
       0

Бихроматическая ближайшая пара, когда R и B разделены вертикальной линией (продолжение)

0 голосов
/ 22 ноября 2011

Ближайшее расстояние между двумя точками (непересекающийся набор)

В задаче о бихроматической ближайшей паре нам дан набор R красных точек и набор B синих точек на плоскости. Проблема состоит в том, чтобы вернуть пару точек, одну красную и одну синюю, расстояние которых минимально для всех пар красно-синих.

Мой алгоритм является своего рода. 

1: If both R and B store only a constant number of points, sort the points according to <y , com- pute a bichromatic closest pair using a brute- force algorithm, and return.

2: Assume |R| >= |B|, otherwise reverse the roles of R and B.

3: Pick a random element r from R.

4: Find the closest element of b in B to r.

5: Compute the left envelope of disks having radius |rb| centered at each of the points in B.

6: Remove all elements of R that are outside the envelope.

Не могу придумать ни одной идеи, которая реализует до 4,5,6.

какая-то ссылка говорит алгоритм Грэма. Я думаю, что это не может быть круг. и я хочу знать, как я их реализую.

а как сделать конверт какого-то региона? Т Т

Легко рисовать на бумаге, но мне всегда сложно реализовать. кто-то, кто советует в C ++?

1 Ответ

2 голосов
/ 22 ноября 2011

Мы все еще используем метрику L1, верно?Давайте предположим, что красные точки имеют x <= 0, а синие точки имеют x> = 0.

Каждая красно-синяя пара имеет кратчайший путь максимум с тремя сегментами: один горизонтальный от красной точки доось y, одна вертикаль по оси y, одна горизонталь от оси y до синей точки.Достаточно вычислить пересечение оси y и диаграммы Вороного для красных точек, а затем найти проекцию каждой синей точки на оси y на диаграмме (например, с помощью двоичного поиска: P; это может быть быстрее,однако, чтобы отсортировать синие точки по y-координате и объединить). 

    |
R****
    *
    *
    ******B
    |
    |y=0

Скажем, красная точка R = (x, y) доминирует другая красная точка R '=(x ', y') тогда и только тогда, когда x '<= x (R, по крайней мере, так же близко к оси y, как R') и ​​| y - y '|<= x - x '. </p>

Лемма 1 Если R доминирует над R', то каждая точка на оси y по крайней мере так же близка к R, как и R '.

Доказательство: пусть P = (x, y ').По существу, по предположению, d (R, P) <= d (R ', P).Для каждой точки Q на оси y d (R ', Q) = d (R', P) + d (P, Q)> = d (R, P) + d (P, Q)> = d(R, Q). 

         |
         Q
         *
R'**P*****
    *    |
    R    |

Лемма 2 Пусть R1 = (x1, y1), R2 = (x2, y2), R3 = (x3, y3).Предположим, что y1 <= y2 <= y3.Если R3 доминирует над R1, то R2 доминирует над R1 или R3 доминирует над R2.Симметрично, если R1 доминирует над R3, то R1 доминирует над R2 или R2 доминирует над R3. </p>

Доказательство: мы имеем x1 <= x3.Есть три случая. </p>

Случай 1: x2

Случай 2: x1 <= x2 <= x3.В этом случае | y2 - y1 |+ | y3 - y2 |= | y3 - y1 |<= x3 - x1 = (x2 - x1) + (x3 - x2), поэтому | y2 - y1 |<= x2 - x1 и R2 доминирует над R1 или | y3 - y2 |<= x3 - x2 и R3 доминирует над R2. </p>

Случай 3: x3

Лемма 3 Предположим, что R доминирует над R 'и R' доминирует над R. Тогда R = R '.

Лемма 4 Предположим, что в R = (x, y) нет доминирующей красной точки.Тогда (0, y) ближе к R, чем любая другая красная точка.

Вместе из лемм следует, что путем многократного устранения всех R 'с некоторым соседом R (в отсортированном порядке по y-координате)который доминирует над R ', мы получаем клетки Вороного по порядку.

...