# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Deterministic Algorithms for 3-D Diameter and some 2-D Lower Envelopes

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Ramos, E. A. (2000). Deterministic Algorithms for 3-D Diameter and some 2-D Lower Envelopes.
In *Proceedings of the 16th Annual Symposium on Computational Geometry (SCG-00)* (pp. 290-299).
New York, USA: ACM Press.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-339E-9

##### 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.