On Vertical Ray Shooting in Arrangements


Jiri Matousek 
Department of Computer Science
Charles University, CSFR
Report B 92-06
February 1992

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-92-06.ps.gz

We consider the following problem: Given a collection $H$ of $n$ hyperplanes in $\Ed$, preprocess it so that given a query point $x$, a hyperplane of $H$ lying immediately above $x$ can be detected quickly. We give a relatively simple solution with $O(n^d/\log^{d-1} n)$ space and deterministic preprocessing time and $O(\log n)$ query time. This gives a slightly more efficient and considerably simplified alternative of a previous solution due to Chazelle and Friedman.

On Vertical Ray Shooting in Arrangements

Jiri Matousek Department of Computer Science Charles University, CSFR Report B 92-06 February 1992