de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

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

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.