Abstract
We derive two results from Clarkson's randomized algorithm for linear programming in a fixed dimension d. The first is a simple general method that reduces the problem of answering linear programming queries to the problem of answering halfspace range queries. For example, this yields a randomized data structure with O(n) space and O(n1-1/[d/2] 20(log(*) n)) query time for linear programming on n halfspaces (d > 3). The second result is a simpler proof of the following: a sequence of q linear programming queries on n halfspaces can be answered in O(n log q) time, if q ≤ nα(d) for a certain constant αd > 0. Unlike previous methods, our algorithms do not require parametric searching.
Original language | English (US) |
---|---|
Pages | 284-290 |
Number of pages | 7 |
DOIs | |
State | Published - 1996 |
Externally published | Yes |
Event | Proceedings of the 1996 12th Annual Symposium on Computational Geometry - Philadelphia, PA, USA Duration: May 24 1996 → May 26 1996 |
Other
Other | Proceedings of the 1996 12th Annual Symposium on Computational Geometry |
---|---|
City | Philadelphia, PA, USA |
Period | 5/24/96 → 5/26/96 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics