1. Tetsuo Asano, Wolfgang Mulzer, Günter Rote, and Yajun Wang:
Constant-work-space algorithms for geometric problems
Journal of Computational Geometry 2 (2011),
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.
Last update: August 22, 2011.