hide
Free keywords:
-
Abstract:
We present a deterministic algorithm for computing the diameter of a set of
$n$ points in $\Re^3$; its running time $O(n\log n)$ is worst-case optimal.
This improves previous deterministic algorithms by
Ramos (1997) and Bespamyatnikh (1998), both with running time
$O(n\log^2 n)$, and matches the running time of a randomized algorithm
by Clarkson and Shor (1989).
We also present a deterministic algorithm for computing the lower envelope
of $n$ functions of 2 variables, for a class of functions with certain
restrictions;
if the functions in the class have lower envelope
with worst-case complexity $O(\lambda_2(n))$, the running time is
$O(\lambda_2(n)
\log n)$, in general, and $O(\lambda_2(n))$ when
$\lambda_2(n)=\Omega(n^{1+\epsilon})$
for any small fraction $\epsilon>0$.
The algorithms follow a divide-and-conquer approach
based on deterministic sampling with the essential feature that planar graph
separators are used to group subproblems in order to limit the growth of the
total subproblem size.
