Querying two boundary points for shortest paths in a polygonal domain (Q419498)

Let \({\mathcal P}\) be a polygonal domain (with holes) in the plane with \(n\) corners. The authors present a data structure that allows for the determination of the shortest path between two points on the boundary \(\partial{\mathcal P}\) in \(O(\log{n})\) time. The shortest path \(\gamma_{u,v}\) between two corners \(u,v\) is necessarily a sequence of line segments adjoining pairs of other corner points, whereas the shortest path between two boundary points \(p,q\) is either the line segment \(\overline{pq}\) or the polygonal path formed from \(\overline{pu}\), \(\overline{vq}\), and \(\gamma_{u,v}\) for some \(u,v\). Using a parametrization \(\alpha\) of \(\partial{\mathcal P}\), the authors write the length of such a path between two boundary points as an algebraic surface \(f_{u,v}(s,t)\), where \(p=\alpha(s)\) and \(q=\alpha(t)\). A data structure used to query the shortest path between two boundary points is then obtained from the minimization diagram \({\mathcal M}\) that computes the lower envelope of the collection of all surfaces \(f_{u,v}\) with \(u,v\) corners of \({\mathcal P}\). It is shown that this structure may be precomputed in \(O(n^{5+\epsilon})\) time, and using the same amount of space. The authors further refine this result by providing a method of computing \({\mathcal M}\) in \(O\bigl(n^4\lambda_{65}(n)\log{n}\bigr)\) time and using \(O\bigl(n^4\lambda_{66}(n)\bigr)\) space, where \(\lambda_m(n)\) is the maximum length of a Davenport--Schinzel sequence of order \(m\) on \(n\) values.