How build a graph with points?

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

Автор DonnieDarko, история, 6 лет назад, По-английски

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?

DonnieDarko
6 лет назад
6

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

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

VastoLorde95

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

← Rev. 2 →

In the worst case the desired graph will have $\text{[math]}$ edges. So you might as well check distance between each pair of points and construct said graph in $\text{[math]}$ .

→ Ответить

DonnieDarko

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

+27

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?

→ Ответить

vlecomte

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

← Rev. 2 →

One (horrible) idea that comes to mind: put the points into square buckets of side $\text{[math]}$ . 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.

→ Ответить

komendart

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

+11

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.

→ Ответить

vlecomte

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

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

→ Ответить

bicsi

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

+42

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.

→ Ответить