Streaming algorithms for extent problems in high dimensions
From MaRDI portal
Publication:2345940
DOI10.1007/s00453-013-9846-4zbMath1314.68392OpenAlexW1985548569MaRDI QIDQ2345940
R. Sharathkumar, Pankaj K. Agarwal
Publication date: 21 May 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-013-9846-4
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (4)
Constant work-space algorithms for facility location problems ⋮ Covering convex polygons by two congruent disks ⋮ Probabilistic smallest enclosing ball in high dimensions via subgradient sampling ⋮ Covering convex polygons by two congruent disks
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimum-volume enclosing ellipsoids and core sets
- Farthest neighbors, maximum spanning trees and related problems in higher dimensions
- The space complexity of approximating the frequency moments
- Improved bounds on weak \(\varepsilon\)-nets for convex sets
- New applications of random sampling in computational geometry
- A subexponential bound for linear programming
- Data streams. Models and algorithms.
- Optimal core-sets for balls
- Faster core-set constructions and data-stream algorithms in fixed dimensions
- Approximating extent measures of points
- Approximate clustering via core-sets
- A space-optimal data-stream algorithm for coresets in the plane
- On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
- Las Vegas algorithms for linear and integer programming when the dimension is small
- Projective clustering in high dimensions using core-sets
- APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
- Communication Complexity
- Numerical linear algebra in the streaming model
- Streaming and Dynamic Algorithms for Minimum Enclosing Balls in High Dimensions
- Coresets for polytope distance
- Approximate minimum enclosing balls in high dimensions using core-sets
- An optimal deterministic algorithm for computing the diameter of a three-dimensional point set
This page was built for publication: Streaming algorithms for extent problems in high dimensions
