1. Tetsuo Asano, Wolfgang Mulzer, Günter Rote, and Yajun Wang:

Constant-work-space algorithms for geometric problems

Journal of Computational Geometry 2 (2011), 46–68.
pdf file (gzipped)

2. Tetsuo Asano and Günter Rote:

Constant-working-space algorithms for geometric problems

In: Proceedings of the 21st Annual Canadian Conference on Computational Geometry, Vancouver, August 17–19, 2009, pp. 87–90. (This is a preliminary short version with parts of the results.)


Constant-work-space algorithms may use only constantly many cells of storage in addition to their input, which is provided as a read-only array. We show how to construct several geometric structures efficiently in the constant-work-space model. Traditional algorithms process the input into a suitable data structure (like a doubly-connected edge list) that allows efficient traversal of the structure at hand. In the constant-work-space setting, however, we cannot afford to do this. Instead, we provide a zero-space data structure that constructs the desired features on the fly by accessing the input. The whole geometric structure can be obtained by using this data structure to enumerate all the features. Of course, we must pay for the space savings by slower running times. While the standard data structure allows us to implement traversal operations in constant time, our schemes typically take linear time to read the input data in each step.

We begin with two simple problems: triangulating a planar point set and finding the trapezoidal decomposition of a simple polygon. In both cases adjacent features can be enumerated in linear time per step, resulting in total quadratic running time to output the whole structure. Actually, we show that the former result carries over to the Delaunay triangulation, and hence the Voronoi diagram. This also means that we can compute the largest empty circle of a planar point set in quadratic time and constant work-space. As another application, we demonstrate how to enumerate the features of an Euclidean minimum spanning tree in quadratic time per step, so that the whole tree can be found in cubic time using constant work-space.

Finally, we describe how to compute a shortest geodesic path between two points in a simple polygon. Although the shortest path problem in general graphs is NL-complete, this constrained problem can be solved in quadratic time using only constant work-space.

pdf file (gzipped)
other papers about this subject
Last update: August 22, 2011.