 |
A Deterministic View of Random Sampling and its Use in Geometry
- Postscript version.
- Dvi version.
- PDF version.
-
Abstract:
The combination of divide-and-conquer and random sampling
has proven very effective in the design of
fast geometric algorithms.
A flurry of efficient probabilistic
algorithms have been recently discovered, based
on this happy marriage. We show that all those algorithms can be
derandomized with only polynomial overhead.
In the process we establish results of independent
interest concerning the covering of
hypergraphs and we improve on various
probabilistic bounds in geometric complexity.
For example, given $n$ hyperplanes in $d$-space and any
integer $r$ large enough, we show how to compute,
in polynomial time, a simplicial packing of size $O\bigl(r^d\bigr)$
which covers $d$-space, each of whose simplices
intersects $O(n /r)$ hyperplanes.
Also, we show how to locate a point among $n$
hyperplanes in $d$-space in $O(\log n)$ query time,
using $O\bigl( n^d\bigr)$ storage and polynomial preprocessing.
|