Two-variable linear programming in parallel

摘要

Two-variable linear programming is a fundamental problem in computational geometry. Sequentially, this problem was solved optimally in linear time by Megiddo and Dyer using the elegant prune-and-search technique. In parallel, the previously best known deterministic algorithm on the EREW PRAM for this problem takes O(log n log log n) time and O(n) work. In this paper, we present a faster parallel deterministic two-variable linear programming algorithm, which takes O(log n log~* n) time and O(n) work on the EREW PRAM. Our algorithm is based on an interesting parallel prune-and-search technique, and makes use of new geometric observations which can be viewed as generalizations of those used by Megiddo and Dyer's sequential algorithms. Our parallel prune-and-search technique also leads to efficient EREW PRAM algorithm for the weighted selection problem, and is likely to be useful in solving other problems.