Parallel algorithms for shortest path problems in polygons (Q1104089)

Given an n-vertex simple polygon \({\mathfrak P}\) we address the following problems: (i) find the shortest path between two points s and d inside \({\mathfrak P}\), and (ii) compute the shortest-path tree between a single point s and each vertex of \({\mathfrak P}\) (which implicitly represents all the shortest paths). We show how to solve the first problem in O(log n) time using O(n) processors, and the more general second problem in \(O(\log^ 2 n)\) time using O(n) processors for any simple polygon \({\mathfrak P}\). We assume the CREW RAM shared memory model of computation in which concurrent reads are allowed, but no two processors should attempt to simultaneously write in the same memory location. The algorithms are based on the divide-and-conquer paradigm and are quite different from the known sequential algorithms.