@inproceedings{67c64a65528748ef90bcea969f1dbe31,
title = "Two-variable linear programming in parallel",
abstract = "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 algorithms for other problems, and is likely to be useful in solving more problems.",
author = "Chen, \{Danny Z.\} and Jinhui Xu",
note = "Publisher Copyright: {\textcopyright} 1998, Springer-Verlag. All rights reserved.; 6th Scandinavian Workshop on Algorithm Theory, SWAT 1998 ; Conference date: 08-07-1998 Through 10-07-1998",
year = "1998",
doi = "10.1007/BFb0054365",
language = "English",
isbn = "3540646825",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "169--180",
editor = "Stefan Arnborg and Lars Ivansson",
booktitle = "Algorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings",
address = "Germany",
}