Item

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.