BOUNDED-INDEPENDENCE DERANDOMIZATION OF GEOMETRIC PARTITIONING WITH APPLICATIONS TO PARALLEL FIXED-DIMENSIONAL LINEAR-PROGRAMMING

We give fast and efficient methods for constructing epsilon-nets and e psilon-approximations for range spaces with bounded VC-exponent. These combinatorial structures have wide applicability to geometric partiti oning problems, which are often used in divide-and-conquer constructio ns in computational geometry algorithms. In addition, we introduce a n ew deterministic set approximation for range spaces with bounded VC-ex ponent, which we call the delta-relative epsilon-approximation, and we show how such approximations can be efficiently constructed in parall el. To demonstrate the utility of these constructions we show how they can be used to solve the linear programming problem in R-d determinis tically in O((log log n)(d)) time using linear work in the PRAM model of computation, for any fixed constant d. Our method is developed for the CRCW variant of the PRAM parallel computation model, and can be ea sily implemented to run in O (log n(log log rt)(d-1)) time using linea r work on an EREW PRAM.