L₁ shortest paths among polygonal obstacles in the plane

We present an algorithm for computing L₁ shortest paths among polygonal obstacles in the plane. Our algorithm employs the “continuous Dijkstra” technique of propagating a “wavefront” and runs in time O(E log n) and space O(E), where n is the number of vertices of the obstacles and E is the number of “events.” By using bounds on the density of certain sparse binary matrices, we show that E = O(n log n), implying that our algorithm is nearly optimal. We conjecture that E = O(n), which would imply our algorithm to be optimal. Previous bounds for our problem were quadratic in time and space. Our algorithm generalizes to the case of fixed orientation metrics, yielding an O(nɛ^−1/2 log²n) time and O(nɛ^−1/2) space approximation algorithm for finding Euclidean shortest paths among obstacles. The algorithm further generalizes to the case of many sources, allowing us to compute an L₁ Voronoi diagram for source points that lie among a collection of polygonal obstacles.