  Let $S$ be a planar $n$-point set. A triangulation for $S$ is a maximal plane
straight-line graph with vertex set $S$. The Voronoi diagram for $S$ is the
subdivision of the plane into cells such that all points in a cell have the
same nearest neighbor in $S$. Classically, both structures can be computed in
$O(n \log n)$ time and $O(n)$ space. We study the situation when the available
workspace is limited: given a parameter $s \in \{1, \dots, n\}$, an
$s$-workspace algorithm has read-only access to an input array with the points
from $S$ in arbitrary order, and it may use only $O(s)$ additional words of
$\Theta(\log n)$ bits for reading and writing intermediate data. The output
should then be written to a write-only structure. We describe a deterministic
$s$-workspace algorithm for computing an arbitrary triangulation of $S$ in time
$O(n^2/s + n \log n \log s )$ and a randomized $s$-workspace algorithm for
finding the Voronoi diagram of $S$ in expected time $O((n^2/s) \log s + n \log
s \log^*s)$.
