Speaker: Sariel Har-Peled (UIUC)

Title: Shortest Path in a Polygon using Sublinear Space

(see http://sarielhp.org/p/14/sublinear_space/ )

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 P with n vertices in a read only memory, and additional
working memory of size m, the new algorithm computes the shortest path
(in P) in O( n^2 / m ) expected time, assuming m=O(n /\log^2 n).  This
requires several new tools, which we believe to be of independent
interest.

Specifically, we show that violator space problems, an abstraction of
low dimensional linear-programming (and LP-type problems), can be
solved using constant space and expected linear time, by modifying
Seidel's linear programming algorithm and using pseudo-random
sequences.