An almost space-optimal streaming algorithm for coresets in fixed dimensions

DOI10.1007/s00453-010-9392-2zbMath1216.68321MaRDI QIDQ547286

Hamid Zarrabi-Zadeh

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

zbMATH Keywords

approximation algorithms; data streams; coresets; geometric optimization problems

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68W25: Approximation algorithms

Related Items

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