## 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(n^{1-1/[d/2]} 2^{0(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 |

State | Published - Jan 1 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