โ Scribed by J. Matousek
No coin nor oath required. For personal study only.
We give an efficient deterministic algorithm for computing (\epsilon)-approximations and (\epsilon)-nets for range spaces of bounded VC-dimension. We assume that an (n)-point range space (\Sigma=(X, X)) of (V C)-dimension (d) is given to us by an oracle, which given a subset (A \subseteq X), returns a list of all distinct sets of the form (A \cap R ; R \in \mathscr{R}) (in time (\left.O\left(|A|^{d+1}\right)\right)). Given a parameter (r), the algorithm computes a ((1 / r))-approximation of size (O\left(r^{2} \log r\right)) for (\Sigma), in time (O\left(n\left(r^{2} \log r\right)^{d}\right)). 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 (E^{d}) and a parameter (r \leqslant n) computes a ( (1 / r))-cutting of (asymptotically optimal) size (O\left(r^{d}\right)). For (r \leqslant n^{1-\delta}), where (\delta>0) is arbitrary but fixed, the running time is (O\left(n r^{d-1}\right)), which is optimal for geometric divide-and-conquer applications. (c) 1995 Academic Press, Inc.
๐ SIMILAR VOLUMES
SUMMARY: Members of the Op Center must race against the clock to prevent the outbreak of war, save the honor of the president and expose the traitors.
SUMMARY: Members of the Op Center must race against the clock to prevent the outbreak of war, save the honor of the president and expose the traitors.
The latest volume in the acclaimed series of high-tech, high-action thrillers. In his position as head of Op-Centre - the National Crisis Management Centre in Washington - Paul Hood has handled emergencies around the world. Now he is facing a potential disaster much closer to home. For the US Presid
EDITORIAL REVIEW: Shadowy elements within the State Department secretly cause tensions to flare between Iran and the former Soviet republic of Azerbaijan. They hope to start a shooting war to increase their own power and profit. At the same time, the conspirators decide to up the ante -- by depo