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

DOI10.1007/s00453-010-9392-2zbMath1216.68321OpenAlexW4242128187MaRDI 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 algorithmsdata streamscoresetsgeometric optimization problems

Mathematics Subject Classification ID

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

Related Items (4)

COMPUTING k CENTERS OVER STREAMING DATA FOR SMALL k ⋮ Communication costs in a geometric communication network ⋮ Approximate Convex Hull of Data Streams ⋮ A streaming algorithm for 2-center with outliers in high dimensions

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

This page was built for publication: An almost space-optimal streaming algorithm for coresets in fixed dimensions