Home | Bookmarks | Papers | Blog |

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.

Last modified: Fri Nov 13 15:43:32 CST 2015