An almost space-optimal streaming algorithm for coresets in fixed dimensions
From MaRDI portal
Publication:547286
DOI10.1007/s00453-010-9392-2zbMath1216.68321MaRDI QIDQ547286
Publication date: 1 July 2011
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.706.5093
68W40: Analysis of algorithms
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
68W25: Approximation algorithms
Related Items
Approximate Convex Hull of Data Streams, Communication costs in a geometric communication network, A streaming algorithm for 2-center with outliers in high dimensions, COMPUTING k CENTERS OVER STREAMING DATA FOR SMALL k
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Farthest neighbors, maximum spanning trees and related problems in higher dimensions
- 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