Approximate Convex Hull of Data Streams

DOI10.4230/LIPIcs.ICALP.2018.21zbMath1499.68408arXiv1712.04564OpenAlexW2963250149MaRDI QIDQ5002691

Vladimir Braverman, Harry Lang, Lin F. Yang, Ananya Kumar, Avrim L. Blum

Publication date: 28 July 2021

Full work available at URL: https://arxiv.org/abs/1712.04564

zbMATH Keywords

convex hullsstreaming algorithmssparse codingepsilon kernels

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Online algorithms; streaming algorithms (68W27)

Related Items (1)

Communication costs in a geometric communication network

Cites Work

• Unnamed Item
• Unnamed Item
• An almost space-optimal streaming algorithm for coresets in fixed dimensions
• Faster core-set constructions and data-stream algorithms in fixed dimensions
• Approximating extent measures of points
• A space-optimal data-stream algorithm for coresets in the plane
• Approximation algorithms for convex hulls
• Sparse Approximation via Generating Point Sets
• Better ϵ-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and ϵ-Kernels

This page was built for publication: Approximate Convex Hull of Data Streams