Article ID: | iaor19981422 |
Country: | United States |
Volume: | 18 |
Issue: | 4 |
Start Page Number: | 397 |
End Page Number: | 420 |
Publication Date: | Dec 1997 |
Journal: | Discrete and Computational Geometry |
Authors: | Goodrich M.T., Ramos E.A. |
Keywords: | geometry |
We give fast and efficient methods for constructing ϵ-nets and ϵ-approximations for range spaces with bounded VC-exponent. These combinatorial structures have wide applicability to geometric partitioning problems, which are often used in divide-and-conquer constructions in computational geometry algorithms. In addition, we introduce a new deterministic set approximation for range spaces with bounded VC-exponent, which we call the δ-relative ϵ-approximation, and we show how such approximations can be efficiently constructed in parallel. To demonstrate the utility of these constructions we show how they can be used to solve the linear programming problem in ℝ