Approximations and Optimal Geometric Divide-and-Conquer

摘要

We give an efficient deterministic algorithm for computing ϵ-approximations and ϵ-nets for range spaces of bounded VC-dimension. We assume that an n-point range space Σ = (X, R) of VC-dimension d is given to us by an oracle, which given a subset A ⊆ X, returns a list of all distinct sets of the form A ∩ R; R ∈ R (in time O(|A|d+1)). Given a parameter r, the algorithm computes a (1/r)-approximation of size O(r2 log r) for Σ, in time O(n(r2 log r)d). A (1/r)-net of size O(r log r) can be computed within the same time bound. We also obtain a new deterministic algorithm which for a given collection H of n hyperplanes in Ed and a parameter r ≤ n computes a (1/r)-cutting of (asymptotically optimal) size O(rd). For r ≤ n1−δ, where δ > 0 is arbitrary but fixed, the running time is O(nrd−1), which is optimal for geometric divide-and-conquer applications.