Closest Point Pair - Codeforces

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

До соревнования
Codeforces Round 947 (Div. 1 + Div. 2)
07:16:34
Зарегистрироваться »

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

→ Трансляции

Round 1975 Div 1 + Div 2 Solution Discussion (with Jan)

Shayan

До начала 10:21:33

Всё →

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

№	Пользователь	Рейтинг
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

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

Всё →

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

№	Пользователь	Вклад
1	maomao90	171
2	adamant	164
3	awoo	163
4	TheScrasse	159
5	nor	157
6	maroonrk	155
7	-is-this-fft-	152
8	Petr	147
9	orz	145
9	pajenegod	145

Всё →

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

→ Прямой эфир

Детальнее →

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

Closest Point Pair

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

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
10 лет назад
18

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

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

sparik

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

+10

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

→ Ответить

RodionGork

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

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

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

+23

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

→ Ответить

RodionGork

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

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

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

← 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

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

← 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

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

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

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

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

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

+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

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

Not so sure now :D

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

→ Ответить

niklasb

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

← Rev. 3 →

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

→ Ответить

gawry

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

← 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

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

"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

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

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

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

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

→ Ответить

dnk

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

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.

→ Ответить