Approximating extent measures of points

By Pankaj Kumar Agarwal, Sariel Har-Peled, Kasturi R. Varadarajan. JACM, 2004

392 citations recorded by the source corpus.

We present a general technique for approximating various descriptors of the extent of a set P of n points in Rd when the dimension d is an arbitrary fixed constant. For a given extent measure μ and a parameter ϵ > 0, it computes in time O(n + 1/ϵO(1)) a subset Q ⊆ P of size 1/ϵO(1), with the property that (1 − ϵ)μ(P) ≤ μ(Q) ≤ μ(P). The specific applications of our technique include ϵ-approximation algorithms for (i) computing diameter, width, and smallest bounding box, ball, and cylinder of P, (ii) maintaining all the previous measures for a set of moving points, and (iii) fitting spheres and cylinders through a point set P. Our algorithms are considerably simpler, and faster in many cases, than previously known algorithms.

Subfields: Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition, Signal Processing

View Paper: https://www.semanticscholar.org/paper/3767d23c17ccdde6abb7cb22568f27ceb927e5b8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Graphics and Computer-Aided Design

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Geometric Approximation Algorithms (2011, methodology): “[AHV04], and the results can be (very slightly) improved by treating hte direction as (d− 1)-dimensional entity, see [AHV04] for details.”
Coresets for Data-efficient Training of Machine Learning Models (2019, methodology): “…nearest-neighbors (Wei et al., 2015), mixture models (Lucic et al., 2017), low rank approximation (Cohen et al., 2017), spectral approximation (Agarwal et al., 2004; Li et al., 2013), Nystrom methods (Agarwal et al., 2004; Musco & Musco, 2017), and Bayesian inference (Campbell & Broderick, 2018).”
Geometric Approximation via Coresets (2007, methodology): “It can be proved [AHV04] that K ⊆ H is an ε-kernel of H if and only if K∗ is an ε-kernel of H∗.”
Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering (2013, neutral): “The IceCube neutrino observatory “searches for neutrinos from the most violent astrophysical sources: events like exploding stars, gamma ray bursts, and cataclysmic phenomena involving black holes and neutron stars.””
Coresets for polytope distance (2009, neutral): “Θ(1/ (d−1)/2) for the extent problem [1].”
Subgradient and sampling algorithms for l1 regression (2005, result): “The approximate hardness of the weighted sample problem is a property analogous to that of “coresets” for other fitting problems.[BHPI02, HPV02, AHPVar , BC02] A novelty here is that while most of the known coreset constructions are for problems where the fit involves minimizing a maximum of distan”
k-Means for Streaming and Distributed Big Sparse Data (2015, background): “Coresets were first suggested in [2] as a way to improve the theoretical running time of existing algorithms.”
Data stream clustering: A survey (2013, methodology): “2012] propose a way of summarizing the data stream by extracting a small set of objects, named coreset [Bādoiu et al. 2002; Agarwal et al. 2004].”
Compressive light field photography using overcomplete dictionaries and optimized projections (2013, background): “A comprehensive survey of coresets can be found in [Agarwal et al. 2004].”
Dataset Condensation with Gradient Matching (2020, methodology): “A classical technique to reducing a large set of high-dimensional points to a small set such that the reduced set approximately preserves a target property ( e.g . width, diameter) of the original data is coreset selection [11, 12, 13].”
DataComp: In search of the next generation of multimodal datasets (2023, background): “A related line of work develops coreset selection algorithms [55, 3, 42, 7, 87, 136, 28], which aim to select data subsets that lead to the same performance as training on the entire dataset.”
Private coresets (2009, methodology): “Coresets have been used to great effect for a vast host of geometric and graph problems, including k-median [11, 25, 31, 32], k-mean [25, 31, 32], k-center [33], subspace approximation [23, 30, 34], shape fitting [2], k-line median [23], k-line center [33, 34], moving points [29], max TSP [27], mini”
Dataset Condensation with Differentiable Siamese Augmentation (2021, background): “Significantly decreasing these costs without degrading the performance of the trained models is one of the long-standing goals in machine learning (Agarwal et al., 2004).”
Core‐sets: An updated survey (2019, background): “The simplest case is where all the weights equal 1, and C is just a subset, which makes sense for covering problems (P. Agarwal et al., 2004; P. K. Agarwal & Har-Peled, 2001).”
BICO: BIRCH Meets Coresets for k-Means Clustering (2013, methodology): “Theoretical analysis has mostly focused on the latter scenario and then relies on the merge & reduce framework originally by Bentley and Saxe [7] and rst applied to clustering in [4].”
On coresets for k-means and k-median clustering (2004, methodology): “Coresets have been used for geometric approximation mainly in low-dimension [1, 18, 2], although a similar but weaker concept was also used in high dimensions [9, 8, 20].”
Relative-Error CUR Matrix Decompositions (2007, background): “Agarwal, Har-Peled, and Varadarajan have analyzed so-called “core sets” as a tool for eﬃciently approximating various extent measures of a point set [3, 4].”