CGAL users discussion list

[Lee Croft <>]

Hi,

Thank you for your response and the excellent reference material. I was
happy to find that your book was available at the library of my university.

If I understand correctly the approach in section 9.3.1 however, it is not
exactly what I am looking for. To my understanding, the free space is
sub-divided into convex cells which are then searched using the
breadth-first search to find a path from the source to the destination. This
however isn't guaranteed to be a shortest path due to the fact that the
cells would not be of uniform size. I suppose that the breadth-first search
could be substituted with a uniform-cost search or Dijkstra's algorithm
using the distances between the cell interiors and vertical edge midpoints
as weights in order to find the shortest path at the cost of a slightly
higher time complexity.

I should explain that the reason I am interested in shortest path algorithms
is due to the fact that I ultimately want to compute a geodesic Voronoi
diagram with polygonal obstacles in a two-dimensional Euclidean plane. Since
a multiple source shortest path map is essentially the same as this type of
Voronoi diagram I am hoping to find something in CGAL which computes a
shortest path map. My appologies for not stating this more clearly.

Thanks,
Lee



--
View this message in context: 
http://cgal-discuss.949826.n4.nabble.com/Two-dimensional-Euclidean-shortest-path-algorithms-in-CGAL-tp4659808p4659817.html
Sent from the cgal-discuss mailing list archive at Nabble.com.