Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop
Show entries of:
this year
(2020) |
last year
(2019) |
two years ago
(2018) |
Notes URL
Action:
login to update
Options:
Goto entry point
Author, Editor
Author(s):
Ramos, Edgar A.
dblp
Editor(s):
BibTeX cite key*:
Ramos1999
Title, Booktitle
Title*:
On range reporting, ray shooting and $k$-level construction
Booktitle*:
Proceedings of the 15th Annual Symposium on Computational Geometry (SCG-99)
Event, URLs
URL of the conference:
URL for downloading the paper:
Event Address*:
Miami Beach, Florida
Language:
English
Event Date*
(no longer used):
June 13-16, 1999
Organization:
Event Start Date:
10 August 2020
Event End Date:
10 August 2020
Publisher
Name*:
ACM
URL:
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
390-399
Year*:
1999
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We describe the following data structures. For halfspace range reporting,
in 3-space using expected preprocessing time $O(n\log n)$, worst case storage
$O(n\log\log n)$ and worst case reporting time $O(\log n+k)$ where $n$ is
the number of data points and $k$ the number of points reported; in $d$-space,
with $d$ even, using worst case preprocessing time $O(n\log n)$ and storage
$O(n)$ and reporting time $O(n^{1-1/\lfloor d/2\rfloor}\log^c n+k)$. For ray
shooting in a convex polytope determined by $n$ facets using deterministic
preprocessing time $O((n/\log n)^{\floor{d/2}}\log^c n)$ and storage $O((n/
\log n)^{\lfloor d/2 \rfloor}2^{\log^* n})$ and with query time $O(\log n)$.
For ray shooting in arbitrary direction among $n$ hyperplanes using preprocessing
$O(n^d/ \log^{\floor{d/2}} n)$ and query time $O(\log n)$. We also
describe algorithms to construct the $k$-level of $n$ planes in 3-space dual
to points in convex position: the first one is randomized and uses nearly optimal
expected time $O(n\log n + nk2^{c\log^* k})$ and the second one is deterministic
and uses time $O(nk\log^c n)$. By a standard geometric transformation the same
time bound applies for the construction of the $k$-order Voronoi diagram of $n$
sites in the plane.
Download
Access Level:
Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat
BibTeX Entry:
@INPROCEEDINGS
{
Ramos1999
,
AUTHOR = {Ramos, Edgar A.},
TITLE = {On range reporting, ray shooting and $k$-level construction},
BOOKTITLE = {Proceedings of the 15th Annual Symposium on Computational Geometry (SCG-99)},
PUBLISHER = {ACM},
YEAR = {1999},
PAGES = {390--399},
ADDRESS = {Miami Beach, Florida},
}
Entry last modified by Uwe Brahm, 03/02/2010
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
03/26/2000 07:36:11 PM
Revisions
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Anja Becker
Anja Becker
Edgar A. Ramos
Edit Dates
04/04/2001 07:43:49 PM
30.03.2000 12:24:03
29.03.2000 16:28:29
26/03/2000 19:36:11