
Sariel Har-Peled.
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 $\Polygon$ with $n$ vertices in a read only memory, and additional working memory of size $\Space$, the new algorithm computes the shortest path (in $\Polygon$) in $O( n^2 /\, \Space )$ expected time. This requires several new tools, which we believe to be of independent interest.
PDF [Printer friendly PDF].
Slides: Talk in TAU, 06/17/15.
Slides: Talk in SoCG 2015, Eindhoven, 06/22/15.