Cutting Hyperplanes for Divide-and-Conquer
Report ID: TR-335-91Author: Chazelle, Bernard
Date: 1991-06-00
Pages: 15
Download Formats: |PDF|
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.