Tetsuo Asano and Günter Rote:
Constant-working-space algorithms for geometric problems
Manuscript, submitted for
publication, Proceedings of the 21st Canadian Conference on Computational
Geometry, Vancouver, August 17–19, 2009, 4 pages.
Abstract
We present an algorithm for constructing the Delaunay triangulation of
n given points in the plane. It runs in
O(n2) time using only constant
working space (more precisely, O(log n) bits in
total) with input data on a read-only array. We apply it to construct
the Voronoi diagram in O(n2) time and
Euclidean minimum spanning tree in
O(n3) time in the same model.
Last update: May 8, 2009.