Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

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.