de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

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.