Faster core-set constructions and data-stream algorithms in fixed dimensions

Research output: Contribution to journalArticlepeer-review

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 enclosing annulus, minimum-width enclosing 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 languageEnglish (US)
Pages (from-to)20-35
Number of pages16
JournalComputational Geometry: Theory and Applications
Volume35
Issue number1-2 SPEC. ISS.
DOIs
StatePublished - Aug 2006
Externally publishedYes

Keywords

  • Approximation algorithms
  • Data streams
  • Geometric optimization problems

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • 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