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
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
