Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer,
Günter Rote, and André Schulz:
Memoryconstrained algorithms for simple polygons

Abstracts of the 28th European Workshop on Computational Geometry
(EuroCG'12), Assisi, Italy, March 2012, pp. 49–52, Editors: Walter
Didimo and Giuseppe Liotta.

Computational Geometry, Theory and Applications 46
(2013), 959–969. Special issue for the 28th European
Workshop on Computational Geometry (EuroCG'12). doi:10.1016/j.comgeo.2013.04.005.
arXiv:1112.5904 [cs.CG].
Abstract
A constantworkspace algorithm has readonly access to an input array and may
use only constantly many additional words of O(log n) bits,
where n is the size of the input. We show that we can find a
triangulation of a plane straightline graph with n vertices in
O(n^{2})
time. We also consider preprocessing a simple ngon,
which is given by the ordered sequence of its vertices, 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.
Last update: January 3, 2012.