Closest Point Pair - Codeforces

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
24:32:09
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя I_love_tigersugar

Closest Point Pair

Автор I_love_tigersugar, 11 лет назад, По-английски

Given N distinct points on the plane. Find the pair of point with the smallest (and largest) Euclid distance between them.

I only know the Brute-Force O(n^2) algorithm to solve this.

Can someone give me any faster algorithm?

Thanks in advance.

geometry, geometry tag

I_love_tigersugar
11 лет назад
18

Комментарии (18)

Написать комментарий?

sparik

11 лет назад, # |

+10

There is a divide-and-conquer solution in O(n*log(n)), but this one is easier to implement,

→ Ответить

RodionGork

11 лет назад, # |

the smallest (and largest)

I thought these are two completely different problems and you should not mix them. I believe the shortest distance could be found efficiently, but it is not so for the greatest one.

→ Ответить

HolyInq

11 лет назад, # ^ |

+23

Convex hull + two pointers on it are O(NlogN) solution to farthest points problem.

→ Ответить

RodionGork

11 лет назад, # ^ |

I agree. I failed to note we are speaking of 2D space, sorry. But I was bewildered by the yellow color of the author's handle (since planar case is discussed in wikipedia). :)

I thought that closest pair algorithm could be generalized for any number of dimensions with the same asymptotic, but not the furthest pair. Though I may be wrong — am I?

→ Ответить

Xellos

11 лет назад, # ^ |

← Rev. 2 →

Largest distance... well, it's between points on a convex hull. Out of points inside triangle $\text{[math]}$ , the one most distant from point $\text{[math]}$ must be $\text{[math]}$ or $\text{[math]}$ .

Also, the distance of vertices of a convex polygon from an arbitrary vertex $\text{[math]}$ of this polygon would (as we travel along the perimeter) first keep increasing and then keep decreasing, so we can bin-search for the first pair of vertices $\text{[math]}$ , $\text{[math]}$ of which the first is farther than the second.

By repeating this for all possible choices of vertex $\text{[math]}$ , we can find the most distant pair in $\text{[math]}$ .

Edit: ninja'd :D

→ Ответить

Igorjan94

11 лет назад, # ^ |

← Rev. 4 →

+10

No need to bin-search. You can find the largest distance between two points on convex hull with rotating calipers method in O(k), where k is count of points in CH. There is good article here, but on russian. You can google-translate it or try to understand the main idea from pictures.

→ Ответить

Xellos

11 лет назад, # ^ |

To everyone their own. I know the rotating calipers method (from CTU Open 2013, one problem was about finding a minimum perimeter bounding rectangle for a set of points), but I'd rather bin-search, because I could code it quickly and painlessly. And you still need to construct the convex hull in $\text{[math]}$ time.

BTW you link is neither clickable nor readable. Maybe it's because of some special characters — anyway, it's better to not use the link as the shown text.

→ Ответить

Igorjan94

11 лет назад, # ^ |

Of course bin-search is easier to implement, and $\text{[math]}$ == $\text{[math]}$ , but if we know that points are on CH, we can compute it in linear time

Yes, I know. idk why old link didn't work, but now shortened link works fine

→ Ответить

gawry

11 лет назад, # ^ |

+21

Are you sure that the distances from a fixed vertex of a convex polygon first increases and then decreases? Say that the polygon is very similar to an ellipsis, and the ellipsis is very thin. Take vertex roughly in the middle, then the distance first increases, then decreases, then increases, and then decreases again.

→ Ответить

Xellos

11 лет назад, # ^ |

Not so sure now :D

I remember that some nice property should hold there, though.

→ Ответить

niklasb

11 лет назад, # ^ |

← Rev. 3 →

I think for points that are part of a maximum distance pair it holds.

→ Ответить

gawry

11 лет назад, # ^ |

← Rev. 2 →

Why? You can have a situation similar to this:

the maximum distance is between the bottom central point and one of the red points. But the red parts can be arbitrarily complicated: you can be within the circle, then outside, then within again, and so on...

→ Ответить

niklasb

11 лет назад, # ^ |

"you can be within the circle, then outside, then within again, and so on" But then the polygon wouldn't be convex would it? That said, I can't prove that what I said is true, but the rotating calipers method makes a very similar assumption it seems (or maybe I'm wrong).

→ Ответить

gawry

11 лет назад, # ^ |

Why wouldn't it be convex? I can repeat the red part multiple times (after scaling down a little bit) and the resulting polygon will still be convex :)

→ Ответить

niklasb

11 лет назад, # ^ |

I see. Clever, I guess this settles the argument :)

→ Ответить

dnk

11 лет назад, # |

You can sort the point first by x-coordinate, then by y-coordinate. Call your current shortest distance D. When go through point P[i], get a set S consist of all point to the left of P[i] which Manhattan distance to P[i] smaller or equal than D. Run brute-force in S. One can prove that S has O(1) size. Good luck.

→ Ответить