If I want to build a graph when the input is a set of points
and an edge exists if the distance between two points is less than
some value x, what is the best way to construct the graph?
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
10:19:15
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
10:19:15
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 07:15:46 (g1).
Десктопная версия, переключиться на мобильную.
При поддержке
In the worst case the desired graph will have
edges. So you might as well check distance between each pair of points and construct said graph in 
.
Thanks man! and in the case that I do not want to build the graph, but put each "component" in a subset, Is there a better approach?
One (horrible) idea that comes to mind: put the points into square buckets of side
. The points within a bucket are clearly linked together. Compute the convex hull in each bucket. Then find the closest distance between the points of a bucket and those of its 12 relevant neighbors with rotating callipers. Link them if that distance is ≤ x.
There are 20 relevant neighbours, but it is no so important.
Don't quite understand how convex hull will help. IMHO the closest pair may be not from convex hulls.
You are right on both fronts (seems like I can't count). Since convex hull doesn't work, you might have to do something like this, which makes the algorithm even more horrible: https://cs.stackexchange.com/questions/65573/closest-pair-of-points-between-two-sets-in-2d
You could conpute the Delaunay triangulation of the points and then consider only edges which correspont to adjacent faces. This works because the Euclidean MST is known to be a subgraph in this (planar) triangulation graph.