2014/12/02 by Sariel Har-Peled, Har-Peled, Sariel
Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.1412.0779
openalex publication_date 2014/12/02 · arxiv created 2015/11/28 · arxiv updated 2015/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
\renewcommand\Re\rm I \hspace-0.025em R \newcommand\SetXX \newcommand\VorX[1]V \pth#1 \newcommand\PolygonP \newcommand\Spacem \newcommand\pth[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 \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( n2 / \Space ) expected time. This requires several new tools, which we believe to be of independent interest.