Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt





On range reporting, ray shooting and $k$-level construction


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

Ramos, E. A. (1999). On range reporting, ray shooting and $k$-level construction. In Proceedings of the 15th Annual Symposium on Computational Geometry (SCG-99) (pp. 390-399). New York, USA: ACM.

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.