### Abstract

We speed up previous (1 + ε)-factor approximation algorithms for a number of geometric optimization problems in fixed dimensions: diameter, width, minimum-radius enclosing cylinder, minimum-width annulus, minimum-volume bounding box, minimum-width cylindrical shell, etc. Linear time bounds were known before; we further improve the dependence of the "constants" in terms of ε. We next consider the data stream model and present new (1 + ε)-factor approximation algorithms that need only constant space for all of the above problems in any fixed dimension. Previously, such a result was known only for diameter. Both sets of results are obtained using the core-set framework recently proposed by Agarwal, Har-Peled, and Varadarajan.

Original language | English (US) |
---|---|

Pages | 152-159 |

Number of pages | 8 |

State | Published - Sep 29 2004 |

Externally published | Yes |

Event | Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States Duration: Jun 9 2004 → Jun 11 2004 |

### Other

Other | Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) |
---|---|

Country | United States |

City | Brooklyn, NY |

Period | 6/9/04 → 6/11/04 |

### Keywords

- Approximation algorithms
- Data streams
- Geometric optimization problems

### ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics

## Fingerprint Dive into the research topics of 'Faster core-set constructions and data stream algorithms in fixed dimensions'. Together they form a unique fingerprint.

## Cite this

*Faster core-set constructions and data stream algorithms in fixed dimensions*. 152-159. Paper presented at Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04), Brooklyn, NY, United States.