Cutting Hyperplanes for Divide-and-Conquer

Abstract:

Given $n$ hyperplanes in $E sup d$, a $1/r)-cutting$ is a collection of
simplices which together cover $E sup d$ and such that the interior of
each simplex intersects at most $n/r$ hyperplanes. We present an
algorithm for computing a $(1/r$-cutting of (asymptotically) minimum
size in $O(nr sup d-1$) time. If, as is the case in practice, the
lists of cutting hyperplanes must be explicitly provided, then the
algorithm is optimal. Our result bridges a gap in a recent algorithm
of Matousek by extending its performance to all values of $r$; the
previous bound was restricted to $r^<=^n sup 1- delta $, for any fixed
$ delta > 0$. To attain our goal, we show that optimal cuttings can be
refined by composition. This is interesting in its own right, because
it leads to the improvement and the simplification of a number of
geometric algorithms, e.g., point location among hyperplanes, counting
segment intersections, Hopcroft's line/point incidence problem, linear
programming in fixed dimension. One of the main tools used in the
cutting construction is a proof that $ epsilon $-approximations can be
used to estimate how many vertices of a hyperplane arrangement fall
inside a given simplex. In a different development, to be reported
elsewhere, we have used this lemma to derive an optimal deterministic
algorithm for computing convex hulls in higher dimensions. Thus, we
suspect that the lemma will have other useful applications in
computational geometry.

This technical report has been published as

Cutting Hyperplanes for Divide-and-Conquer. Bernard Chazelle,
Discrete and Computational Geometry,
9, 1993, pp. 145-158.