Time and space efficient algorithms for shortest paths between convex polygons (Q1098634)

Two algorithms are presented for computing shortest paths in the plane avoiding convex polygon obstacles. For the first algorithm the obstacles are assumed to consist of f disjoint convex polygons, for the second algorithm the boundaries of the f polygons may intersect pairwise at most twice. For finding the shortest path between two arbitrary query points the first algorithm takes time O(f n log n) and space O(n), the second algorithm preprocesses the polygons in time O(n log n\(+f\) 3) and space \(O(n+f\) 2). Thereafter one query takes time O(n log n\(+f\) 2).