de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

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

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45255

Ramos,  Edgar A.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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