%0 Journal Article
%T Memory-Constrained Algorithms for Simple Polygons
%A Tetsuo Asano
%A Kevin Buchin
%A Maike Buchin
%A Matias Korman
%A Wolfgang Mulzer
%A G¨¹nter Rote
%A Andr¨¦ Schulz
%J Computer Science
%D 2011
%I arXiv
%R 10.1016/j.comgeo.2013.04.005
%X A constant-workspace algorithm has read-only access to an input array and may use only O(1) additional words of $O(\log n)$ bits, where $n$ is the size of the input. We assume that a simple $n$-gon is given by the ordered sequence of its vertices. We show that we can find a triangulation of a plane straight-line graph in $O(n^2)$ time. We also consider preprocessing a simple polygon for shortest path queries when the space constraint is relaxed to allow $s$ words of working space. After a preprocessing of $O(n^2)$ time, we are able to solve shortest path queries between any two points inside the polygon in $O(n^2/s)$ time.
%U http://arxiv.org/abs/1112.5904v2