de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

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

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45255

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-339E-9
Zusammenfassung
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.