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.


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.

  PostScript file (gzipped)   pdf file (gzipped)
other papers about this subject
Last update: May 8, 2009.