Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote, and André Schulz:

Memory-constrained algorithms for simple polygons

  1. Abstracts of the 28th European Workshop on Computational Geometry (EuroCG'12), Assisi, Italy, March 2012, pp. 49–52, Editors: Walter Didimo and Giuseppe Liotta.
  2. 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].


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.

  pdf file (gzipped)
other papers about this subject
Last update: January 3, 2012.