0
$\begingroup$

The problem is the following: Given $n$ points in $\mathbb{R^2}$, give an algorithm that given points $u$ and $v$, $u \neq v$ find a sequence of points such you can go from $u$ to $v$ and in each step you move $t$, with $t \in [1,2]$.

At first I was thinking to use the Delaunay Triangulation, and eliminate the edges such that the length of that edge is not in the range. However, you can have points really close and then you are going to delete everything.

Another thing is that you can go to a node really close if there is a route that goes away and the returns.

How can I tackle this problem?

$\endgroup$
5
  • $\begingroup$ Build a graph from your set of points: each point correspond to a node, and two nodes are connected iff the distance between them is between $1$ and $2$. Your question amounts to finding a path connecting $u$ and $v$ within that graph, which can be done with Dijkstra's algorithm or $A^*$. $\endgroup$
    – Ben Grossmann
    Nov 15, 2022 at 19:48
  • $\begingroup$ Thats the first I think of, but I think you can do better. Because you can use an euclidian triangulation like delaunay triangulation and the process the edges if they are too short maybe merge various edges. $\endgroup$
    – Tommy do Nascimiento
    Nov 15, 2022 at 20:00
  • $\begingroup$ I don't see why a triangulation would allow you to "do better" here $\endgroup$
    – Ben Grossmann
    Nov 15, 2022 at 20:03
  • $\begingroup$ How do you know such a path exists? $\endgroup$
    – copper.hat
    Nov 15, 2022 at 20:15
  • $\begingroup$ You dont know. Is possible to not exists, I guess. $\endgroup$
    – Tommy do Nascimiento
    Nov 15, 2022 at 20:17

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .