Publications

### Server    domino.mpi-inf.mpg.de

 Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop
 Author, Editor
 Author(s): Ramos, Edgar A. dblp
 Editor(s):
 BibTeX cite key*: Ramos2000c
 Title, Booktitle
 Title*: Deterministic Algorithms for 3-D Diameter and some 2-D Lower Envelopes Booktitle*: Proceedings of the 16th Annual Symposium on Computational Geometry (SCG-00)
 Event, URLs
 Conference URL:: http://www.cs.ust.hk/tcsc/scg00.html Downloading URL: http://www.mpi-sb.mpg.de/~ramos Event Address*: Clear Water Bay, Kowloon, Hong Kong Language: English Event Date* (no longer used): June 12-14, 2000 Organization: Association of Computing Machinery (ACM) Event Start Date: 12 June 2000 Event End Date: 14 June 2000
 Publisher
 Name*: ACM Press URL: Address*: New York, USA Type:
 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: June Pages: 290-299 Year*: 2000 VG Wort Pages: ISBN/ISSN: Sequence Number: DOI:
 (LaTeX) 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. Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: Expert Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{Ramos2000c,
AUTHOR = {Ramos, Edgar A.},
TITLE = {Deterministic Algorithms for 3-D Diameter and some 2-D Lower Envelopes},
BOOKTITLE = {Proceedings of the 16th Annual Symposium on Computational Geometry (SCG-00)},
PUBLISHER = {ACM Press},
YEAR = {2000},
ORGANIZATION = {Association of Computing Machinery (ACM)},
PAGES = {290--299},
ADDRESS = {Clear Water Bay, Kowloon, Hong Kong},
MONTH = {June},
}