Article

No, coreset, no cry

Author:

Sariel Har-PeledAuthors Info & Claims

FSTTCS'04: Proceedings of the 24th international conference on Foundations of Software Technology and Theoretical Computer Science

Pages 324 - 335

https://doi.org/10.1007/978-3-540-30538-5_27

Published: 16 December 2004 Publication History

Abstract

We show that coresets do not exist for the problem of 2-slabs in ${\mathbb R}^{3}$, thus demonstrating that the natural approach for solving approximately this problem efficiently is infeasible. On the positive side, for a point set P in ${\mathbb R}^{3}$, we describe a near linear time algorithm for computing a (1+ε)-approximation to the minimum width 2-slab cover of P. This is a first step in providing an efficient approximation algorithm for the problem of covering a point set with k-slabs.

References

[1]

Agarwal, P.K., Sharir, M.: Efficient algorithms for geometric optimization. ACMComput. Surv. 30 (1998) 412-458

Digital Library

[2]

Bern, M., Eppstein, D.: Approximation algorithms for geometric problems. InHochbaum, D.S., ed.: Approximationg algorithms for NP-Hard problems. PWSPublishing Company (1997) 296-345

Digital Library

[3]

Agarwal, P.K., Aronov, B., Sharir, M.: Computing envelopes in four dimensionswith applications. SIAM J. Comput. 26 (1997) 1714-1732

Digital Library

[4]

Agarwal, P.K., Sharir, M.: Efficient randomized algorithms for some geometricoptimization problems. Discrete Comput. Geom. 16 (1996) 317-337

Digital Library

[5]

Agarwal, P.K., Sharir, M., Toledo, S.: Applications of parametric searching ingeometric optimization. J. Algorithms 17 (1994) 292-318

Digital Library

[6]

Ebara, H., Fukuyama, N., Nakano, H., Nakanishi, Y.: Roundness algorithms usingthe Voronoi diagrams. In: Proc. 1rd Canad. Conf. Comput. Geom. (1989) 41

[7]

Edelsbrunner, H., Guibas, L.J., Stolfi, J.: Optimal point location in a monotonesubdivision. SIAM J. Comput. 15 (1986) 317-340

Digital Library

[8]

García-Lopez, J., Ramos, P., Snoeyink, J.: Fitting a set of points by a circle.Discrete Comput. Geom. 20 (1998) 389-402

[9]

Le, V.B., Lee, D.T.: Out-of-roundness problem revisited. IEEE Trans. PatternAnal. Mach. Intell. PAMI-13 (1991) 217-223

Digital Library

[10]

Mehlhorn, K., Shermer, T.C., Yap, C.K.: A complete roundness classificationprocedure. In: Proc. 13th Annu. ACM Sympos. Comput. Geom. (1997) 129-138

Digital Library

[11]

Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction.Springer-Verlag, New York, NY (1985)

Digital Library

[12]

Rivlin, T.J.: Approximating by circles. Computing 21 (1979) 93-104

[13]

Roy, U., Liu, C.R., Woo, T.C.: Review of dimensioning and tolerancing: Representationand processing. Comput. Aided Design 23 (1991) 466-483

[14]

Roy, U., Zhang, X.: Establishment of a pair of concentric circles with the minimumradial separation for assessing roundness error. Comput. Aided Design 24 (1992)161-168

[15]

Shermer, T.C., Yap, C.K.: Probing for near centers and relative roundness. In:Proc. ASME Workshop on Tolerancing and Metrology. (1995)

[16]

Smid, M., Janardan, R.: On the width and roundness of a set of points in theplane. Internat. J. Comput. Geom. Appl. 9 (1999) 97-108

[17]

Yap, C.K., Chang, E.C.: Issues in the metrology of geometric tolerancing. InLaumond, J.P., Overmars, M.H., eds.: Robotics Motion and Manipulation. A. K.Peters (1997) 393-400

[18]

Chan, T.M.: Approximating the diameter, width, smallest enclosing cylinder andminimum-width annulus. Internat. J. Comput. Geom. Appl. 12 (2002) 67-85

[19]

Agarwal, P.K., Aronov, B., Har-Peled, S., Sharir, M.: Approximation and exactalgorithms for minimum-width annuli and shells. Discrete Comput. Geom. 24(2000) 687-705

Digital Library

[20]

Agarwal, P.K., Har-Peled, S., Varadarajan, K.R.: Approximating extent measuresof points. J. ACM 51 (2004) 606-635

Digital Library

[21]

Gonzalez, T.: Clustering to minimize the maximum intercluster distance. Theoret.Comput. Sci. 38 (1985) 293-306

[22]

Agarwal, P.K., Procopiuc, C.M.: Exact and approximation algorithms for clustering.Algorithmica 33 (2002) 201-226

Digital Library

[23]

Agarwal, P.K., Procopiuc, C.M., Varadarajan, K.R.: Approximation algorithms fork-line center. In: Proc. 10th Annu. European Sympos. Algorithms. (2002) 54-63

Digital Library

[24]

Megiddo, N.: On the complexity of some geometric problems in unbounded dimension.J. Symb. Comput. 10 (1990) 327-334

Digital Library

[25]

Har-Peled, S., Varadarajan, K.R.: High-dimensional shape fitting in linear time.Discrete Comput. Geom. 32 (2004) 269-288

Digital Library

[26]

Megiddo, N., Tamir, A.: On the complexity of locating linear facilities in the plane.Oper. Res. Lett. 1 (1982) 194-197

Digital Library

[27]

Bădoiu, M., Clarkson, K.L.: Optimal core-sets for balls. In: Proc. 14th ACM-SIAMSympos. Discrete Algorithms. (2003) 801-802

Digital Library

[28]

Har-Peled, S., Varadarajan, K.R.: Projective clustering in high dimensions usingcore-sets. In: Proc. 18th Annu. ACM Sympos. Comput. Geom. (2002) 312-318

Digital Library

[29]

Bădoiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In:Proc. 34th Annu. ACM Sympos. Theory Comput. (2002) 250-257

Digital Library

[30]

Kumar, P., Mitchell, J.S.B., Yildirim, E.A.: Fast smallest enclosing hyperspherecomputation. In: Proc. 5th Workshop Algorithm Eng. Exper. (2003) to appear

[31]

Har-Peled, S., Wang, Y.: Shape fitting with outliers. SIAM J. Comput. 33 (2004)269-285

Digital Library

[32]

Har-Peled, S.: Clustering motion. Discrete Comput. Geom. 31 (2004) 545-565

Digital Library

[33]

Houle, M.E., Toussaint, G.T.: Computing the width of a set. IEEE Trans. PatternAnal. Mach. Intell. PAMI-10 (1988) 761-765

Digital Library

Cited By

Maalouf AStatman AFeldman DGupta RLiu YShah MRajan STang JPrakash B(2020)Tight Sensitivity Bounds For Smaller CoresetsProceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3394486.3403256(2051-2061)Online publication date: 23-Aug-2020
https://dl.acm.org/doi/10.1145/3394486.3403256
Har-Peled SRaichel B(2015)Net and PruneJournal of the ACM10.1145/283123062:6(1-35)Online publication date: 10-Dec-2015
https://dl.acm.org/doi/10.1145/2831230
Feldman DSchmidt MSohler CKhanna S(2013)Turning big data into tiny dataProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627920(1434-1453)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627920
Show More Cited By

Recommendations

Coreset for line-sets clustering
NIPS '22: Proceedings of the 36th International Conference on Neural Information Processing Systems

The input to the line-sets k-median problem is an integer k ≥ 1, and a set L = {L₁, ..., L_n} that contains n sets of lines in ℝ^d. The goal is to compute a set C of k centers (points in ℝ^d) that minimizes the sum $\sum_{L \in \mathcal{L}}\min_{\ell\in L, ...
Towards a theory of meaningfulness and truth: an introduction to variational semantics
No coreset, no cry: II
FSTTCS '05: Proceedings of the 25th international conference on Foundations of Software Technology and Theoretical Computer Science

Let P be a set of n points in d-dimensional Euclidean space, where each of the points has integer coordinates from the range [−Δ, Δ], for some Δ ≥ 2. Let ε > 0 be a given parameter. We show that there is subset Q of P, whose size is polynomial in (log Δ)...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

FSTTCS'04: Proceedings of the 24th international conference on Foundations of Software Technology and Theoretical Computer Science

December 2004

530 pages

ISBN:3540240586

Editors:
Kamal Lodaya
The Institute of Mathematical Sciences, CIT Campus, Chennai, India
,
Meena Mahajan
The Institute of Mathematical Sciences, CIT Campus, Chennai, India

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 16 December 2004

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Maalouf AStatman AFeldman DGupta RLiu YShah MRajan STang JPrakash B(2020)Tight Sensitivity Bounds For Smaller CoresetsProceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3394486.3403256(2051-2061)Online publication date: 23-Aug-2020
https://dl.acm.org/doi/10.1145/3394486.3403256
Har-Peled SRaichel B(2015)Net and PruneJournal of the ACM10.1145/283123062:6(1-35)Online publication date: 10-Dec-2015
https://dl.acm.org/doi/10.1145/2831230
Feldman DSchmidt MSohler CKhanna S(2013)Turning big data into tiny dataProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627920(1434-1453)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627920
Har-Peled SRaichel BBoneh DRoughgarden TFeigenbaum J(2013)Net and pruneProceedings of the forty-fifth annual ACM symposium on Theory of Computing10.1145/2488608.2488684(605-614)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1145/2488608.2488684
Feldman DSchulman L(2012)Data reduction for weighted and outlier-resistant clusteringProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095222(1343-1354)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095222
Varadarajan KXiao X(2012)A near-linear algorithm for projective clustering integer pointsProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095221(1329-1342)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095221
Feldman DLangberg MFortnow LVadhan S(2011)A unified framework for approximating and clustering dataProceedings of the forty-third annual ACM symposium on Theory of computing10.1145/1993636.1993712(569-578)Online publication date: 6-Jun-2011
https://dl.acm.org/doi/10.1145/1993636.1993712
Chan T(2009)Dynamic CoresetsDiscrete & Computational Geometry10.5555/3116272.311651442:3(469-488)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.5555/3116272.3116514
Feldman DFiat AKaplan HNissim KMitzenmacher M(2009)Private coresetsProceedings of the forty-first annual ACM symposium on Theory of computing10.1145/1536414.1536465(361-370)Online publication date: 31-May-2009
https://dl.acm.org/doi/10.1145/1536414.1536465
Chan TTeillaud M(2008)Dynamic coresetsProceedings of the twenty-fourth annual symposium on Computational geometry10.1145/1377676.1377680(1-9)Online publication date: 9-Jun-2008
https://dl.acm.org/doi/10.1145/1377676.1377680
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents