Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer,
Günter Rote, and André Schulz:
Memory-constrained 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 constant-workspace algorithm has read-only 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 straight-line graph with n vertices in
O(n2)
time. We also consider preprocessing a simple n-gon,
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(n2)
time, we are able to
solve shortest path queries between any two points inside the polygon in
O(n2/s) time.
Last update: January 3, 2012.