Bounded-independence derandomization of geometric partitioning with applications to parallel fixed-dimensional linear programming

Bounded-independence derandomization of geometric partitioning with applications to parallel fixed-dimensional linear programming

0.00 Avg rating0 Votes
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: ,
Keywords: geometry
Abstract:

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 ℝd deterministically 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 easily implemented to run in O(log n(log log n)d–1) time using linear work on an EREW PRAM.

Reviews

Required fields are marked *. Your email address will not be published.