An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions

DOI10.1007/978-3-540-87744-8_68zbMath1158.68557OpenAlexW2120871456MaRDI QIDQ3541136

Hamid Zarrabi-Zadeh

Publication date: 25 November 2008

Published in: Algorithms - ESA 2008 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-87744-8_68

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (3)

Dynamic coresets ⋮ Streaming and dynamic algorithms for minimum enclosing balls in high dimensions ⋮ Streaming with minimum space: an algorithm for covering by two congruent balls

Cites Work

• Unnamed Item
• Unnamed Item
• Farthest neighbors, maximum spanning trees and related problems in higher dimensions
• Metric entropy of some classes of sets with differentiable boundaries
• Faster core-set constructions and data-stream algorithms in fixed dimensions
• Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions
• Approximating extent measures of points
• On coresets for k-means and k-median clustering
• Coresets in dynamic geometric data streams
• A space-optimal data-stream algorithm for coresets in the plane
• Decomposable searching problems I. Static-to-dynamic transformation
• Shape Fitting with Outliers
• Practical methods for shape fitting and kinetic data structures using core sets
• Robust shape fitting via peeling and grating coresets

This page was built for publication: An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions