Cutting hyperplane arrangements
Jiřı́ Matoušek · 1990
We will consider an arrangement H of n hyperplanes in Ed (where the dimension d is fixed). An ε-cutting for H will be a collection of (possibly unbounded) d-dimensional simplices with disjoint interiors, which cover all Ed and such that the interior of any simplex is intersected by at most εn hyperplanes of H. We give a deterministic algorithm, finding a (1/r)-cutting with 𝒪(rd(log r)C) simplices in time 𝒪(n(log n)Ard-1 (log r)B) (A,B,C are constants dependent on dimension). In a similar time bound (with an additional 𝒪(r𝒪(1)) overhead) we can also find a (1/r)-net for the range space (X, H(X)), where X is a n-point set in Ed and H(X) denotes the set of all subsets of X which can be cut by a halfspace. This (1/r)-net has size 𝒪(r log r), which matches the best known existence result; in fact, the method gives a constructive existence proof.