MPI-INF Logo
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:
Note, Abstract, ©
(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},
}

Entry last modified by Uwe Brahm, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Edgar A. Ramos		Created
02/23/2001 17:26:12
Revisions
5.
4.
3.
2.
1.		Editor(s)
Uwe Brahm
Uwe Brahm
Anja Becker
Anja Becker
Anja Becker		Edit Dates
02/14/2005 09:32:12 PM
02/14/2005 09:31:54 PM
20.03.2001 17:04:53
20.03.2001 15:53:19
14.03.2001 14:07:18