## 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`(`n`^{2}) 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`(`n`^{2}) time and
Euclidean minimum spanning tree in
`O`(`n`^{3}) time in the same model.
Last update: May 8, 2009.