Shortest Path in a Polygon using Sublinear Space

Original · EN

I-0.025em R X [1]V #1 P m [2][]#1(#2) We resolve an open problem due to Tetsuo Asano, showing how to compute the shortest path in a polygon, given in a read only memory, using sublinear space and subquadratic time. Specifically, given a simple polygon with n vertices in a read only memory, and additional working memory of size, the new algorithm computes the shortest path (in) in O(n² /) expected time. This requires several new tools, which we believe to be of independent interest.