Shortest Path Bounded By Circles

user_12901331 0
Viewed 208

There are n circles with radius r, the origin of the i-th circle is located at (x[i], y[i]). I would like to find the distance of the shortest path from the origin of the first circle to the origin of the last circle, and any point on the path is located inside one or more circle.

Below is a demonstration for three circles located at (3, 3), (3, 7) and (6, 7), the blue line is the shortest path.

image

I have tried to find the intersections of each pair of circles and run a shortest path algorithm, however that result in a time complexity of O(n^5). I would like to know if there exists a better algorithm that runs faster. Thanks.

shortest-path computational-geometry geometry algorithm
1 Answers

I found a solution of O(n^3). Notice the optimal path is made up of line segments joining the starting point, the ending point, or the intersections of circles which do not lie inside another circle (in other words, the "outside intersections" of the graph). The number of candidate points is O(n).

Then for each pair of points, if the every point on the straight line connecting them lies inside the figure, mark the distance of this pair of points to be the straight line distance between them. Otherwise, mark the distance as infinity. This takes O(n^3) as there are O(n^2) pairs of points and the check takes O(n).

Finally, run any shortest path algorithm from the starting position to the ending position. Floyd-Warshall would be a nice choice because its time complexity is O(n^3) and the adjacency matrix is given.

user_129013310
Related