The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
Geometric Approximation via Coresets
Abstract
The paradigm of coresets has recently emerged as a powerful tool for efficiently approximating various extent measures of a point set P. Using this paradigm, one quickly computes a small subset Q of P, called a coreset, that approximates the original set P and and then solves the problem on Q using a relatively inefficient algorithm. The solution for Q is then translated to an approximate solution to the original point set P. This paper describes the ways in which this paradigm has been successfully applied to various optimization and extent measure problems. 1. Introduction One of the classical techniques in developing approximation algorithms is the extraction of “small” amount of “most relevant” information from the given data, and performing the computation on this extracted data. Examples of the use of this technique in a geometric context include random sampling [Chazelle 2000; Mulmuley 1993], convex approximation [Dudley 1974; Bronshteyn and Ivanov 1976], surface simplification [Heckbert and Garland 1997], feature extraction and shape descriptors [Dryden and Mardia 1998; Costa and Cesar 2001]. For geometric problems where the input is a set of points, the question reduces to finding a small subset (a coreset) of the points, such that one can perform the desired computation on the coreset. As a concrete example, consider the problem of computing the diameter of a point set. Here it is clear that, in the worst case, classical sampling techniques like ϵ -approximation and ϵ -net would fail to compute a subset of points that contain a good approximation to the diameter [Vapnik and Chervonenkis 1971; Haussler and Welzl 1987].
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
Golub, G. H., & Loan, C. F. V. (1996) · Johns Hopkins University Press eBooks · Cited by 6,027
Geometric Algorithms and Combinatorial Optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1988) · Algorithms and Combinatorics · doi:10.1007/978-3-642-97881-4 · Cited by 3,431
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
Vapnik, V. N., & Chervonenkis, A. Y. (2015) · Measures of Complexity · doi:10.1007/978-3-319-21852-6_3 · Cited by 3,105
Statistical shape analysis: clustering, learning, and testing
Srivastava, A., Joshi, S. H., Mio, W., & Liu, X. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.86 · Cited by 2,727
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1998) · Journal of the ACM · doi:10.1145/293347.293348 · Cited by 2,300
Clustering to minimize the maximum intercluster distance
Gonzalez, T. F. (1985) · Theoretical Computer Science · doi:10.1016/0304-3975(85)90224-5 · Cited by 1,717
ɛ-nets and simplex range queries
Haussler, D., & Welzl, E. (1987) · Discrete & Computational Geometry · doi:10.1007/bf02187876 · Cited by 723
Mammone, A., Turchi, M., & Cristianini, N. (2009) · WIREs Computational Statistics · doi:10.1002/wics.49 · Cited by 699
Survey of Polygonal Surface Simplification Algorithms
Heckbert, P. S., & Garland, M. (1997) · Cited by 486
Optimal algorithms for approximate clustering
Feder, T., & Greene, D. (1988) · doi:10.1145/62212.62255 · Cited by 437
The discrepancy method: randomness and complexity
(2002) · Choice Reviews Online · doi:10.5860/choice.40-2215 · Cited by 347
Decomposable searching problems
Bentley, J. L. (1979) · Information Processing Letters · doi:10.1016/0020-0190(79)90117-0 · Cited by 340
Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions
Barequet, G., & Har-Peled, S. (2001) · Journal of Algorithms · doi:10.1006/jagm.2000.1127 · Cited by 287
Self-citationA Simple Linear Time (1+ ∊) -Approximation Algorithm for k-Means Clustering in Any Dimensions
Kumar, A., Sabharwal, Y., & Sen, S. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.7 · Cited by 247
Exact and Approximation Algorithms for Clustering
Agarwal, P. K., & Procopiuc, C. M. (2002) · Algorithmica · doi:10.1007/s00453-001-0110-y · Cited by 242
Self-citationANN: library for approximate nearest neighbor searching
Arya, S., & Mount, D. M. (1998) · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · Cited by 209
Metric Entropy of Some Classes of Sets with Differentiable Boundaries
Dudley, R. M. (2010) · Springer eBooks · doi:10.1007/978-1-4419-5821-1_26 · Cited by 189
Bâdoiu, M., & Clarkson, K. L. (2007) · Computational Geometry · doi:10.1016/j.comgeo.2007.04.002 · Cited by 175
Optimally Cutting a Surface into a Disk
Erickson, J., & Har-Peled, S. (2003) · Discrete & Computational Geometry · doi:10.1007/s00454-003-2948-z · Cited by 175
Self-citationApproximation schemes for clustering problems
de la Véga, W. F., Karpiński, M., Mathieu, C., & Rabani, Y. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780550 · Cited by 163
Smaller coresets for k-median and k-means clustering
Har-Peled, S., & Kushal, A. (2005) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/1064092.1064114 · Cited by 102
Self-citationCoresets for $k$-Means and $k$-Median Clustering and their ApplicationsPreprint
Har-Peled, S., & Mazumdar, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.12826 · Cited by 100
Self-citationHar-Peled, S. (2004) · Discrete & Computational Geometry · doi:10.1007/s00454-004-2822-7 · Cited by 75
Self-citationMinimum Enclosing Polytope in High DimensionsPreprint
Panigrahy, R. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0407020 · Cited by 34
Cited by
Towards Total Recall in Industrial Anomaly Detection
Roth, K., Pemula, L., Zepeda, J., Scholkopf, B., Brox, T., & Gehler, P. (2022) · 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr52688.2022.01392 · Cited by 1,810
Map-matching for low-sampling-rate GPS trajectories
Lou, Y., Zhang, C., Zheng, Y., Xie, X., Wang, W., & Huang, Y. (2009) · Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems · doi:10.1145/1653771.1653820 · Cited by 797
Data Streams: Algorithms and Applications
Muthukrishnan, S. (2005) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000002 · Cited by 718
Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
Clarkson, K. L. (2010) · ACM Transactions on Algorithms · doi:10.1145/1824777.1824783 · Cited by 379
FAPM: Fast Adaptive Patch Memory for Real-Time Industrial Anomaly Detection
Kim, D., Park, C., Cho, S., & Lee, S. (2023) · ICASSP 2023 - 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) · doi:10.1109/icassp49357.2023.10096400 · Cited by 56
Metadata
- Authors
- Agarwal, P. K., Har-Peled, S., & Varadarajan, K. R.
- Venue
- Combinatorial and Computational Geometry
- Publisher
- Cambridge University Press
- Published
- 2005-08-08
- Pages
- 1-30
- OpenAlex
- W2247953682
- Cited by
- 256
- References
- 25
- Type
- other
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.