Abstract
We describe general randomized reductions of certain geometric optimization problems to their corresponding decision problems. These reductions increase the expected time complexity by only a constant factor and eliminate extra logarithmic factors in previous approaches. Improved algorithms are thus obtained for a variety of problems in computational geometry: finding minimal k-point subsets, matching point sets under translation, and solving problems related to p-centers and linear programming with violations.
| Original language | English (US) |
|---|---|
| Pages | 269-278 |
| Number of pages | 10 |
| DOIs | |
| State | Published - 1998 |
| Externally published | Yes |
| Event | Proceedings of the 1998 14th Annual Symposium on Computational Geometry - Minneapolis, MN, USA Duration: Jun 7 1998 → Jun 10 1998 |
Other
| Other | Proceedings of the 1998 14th Annual Symposium on Computational Geometry |
|---|---|
| City | Minneapolis, MN, USA |
| Period | 6/7/98 → 6/10/98 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics