Article

Faster core-set constructions and data stream algorithms in fixed dimensions

Author:

Timothy M. ChanAuthors Info & Claims

SCG '04: Proceedings of the twentieth annual symposium on Computational geometry

Pages 152 - 159

https://doi.org/10.1145/997817.997843

Published: 08 June 2004 Publication History

Abstract

We speed up previous (1+ε)-factor approximation algorithms for a number of geometric optimization problems in fixed dimensions: diameter, width, minimum-radius enclosing cylinder, minimum-width annulus, minimum-volume bounding box, minimum-width cylindrical shell, etc. Linear time bounds were known before we further improve the dependence of the "constants" in terms of ε.We next consider the data stream model and present new (1+ε)-factor approximation algorithms that need only constant space for all of the above problems in any fixed dimension. Previously, such a result was known only for diameter.Both sets of results are obtained using the core-set framework recently proposed by Agarwal, Har-Peled, and Varadarajan.

References

[1]

P. K. Agarwal, B. Aronov, and M. Sharir. Line transversals of balls and smallest enclosing cylinders in three dimensions. Discrete Comput. Geom. 21:373--388, 1999.

[2]

P. K. Agarwal, L. J. Guibas, S. Har-Peled, A. Rabinovitch, and M. Sharir. Computing the penetration depth of two convex polytopes in 3D. Nordic J. Comput. 7:227--240, 2000.

Digital Library

[3]

P. K. Agarwal, S. Krishnan, N. H. Mustafa, and S. Venkatasubramanian. In Proc. 11th European Sympos. Algorithms Lect. Notes Comput. Sci., vol. 2832, Springer-Verlag, pages 544--555, 2003.

[4]

P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. Approximating extent measures of points. http://-valis.cs.uiuc.edu/~sariel/research/papers/01/-fitting/, 2003. Preliminary versions appeared in Proc. 12th ACM-SIAM Sympos. Discrete Algorithms pages 148--157, 2001; Proc. 42nd IEEE Sympos. Found. Comput. Sci., pages 66--73, 2001.

Digital Library

[5]

P. K. Agarwal, J. Matoušek, and S. Suri. Farthest neighbors, maximum spanning trees and related problems in higher dimensions. Comput. Geom. Theory Appl., 1:189--201, 1992.

Digital Library

[6]

S. Arya, T. Malamatos, and D. M. Mount. Space-efficient approximate Voronoi diagrams. In Proc. 34th ACM Sympos. Theory Comput., pages 721--730, 2002.

Digital Library

[7]

M. Bǎdoiu and K. L. Clarkson. Optimal core-sets for balls. http://cm.bell-labs.com/who/clarkson/-pubs.html, 2003. Preliminary version in Proc. 14th ACM-SIAM Sympos. Discrete Algorithms pages 801--802, 2003.

Digital Library

[8]

M. Bǎdoiu, S. Har-Peled, and P. Indyk. Approximate clustering via core-sets. In Proc. 34th ACM Sympos. Theory Comput., pages 250--257, 2002.

Digital Library

[9]

G. Barequet and S. Har-Peled. Efficiently approximating the minimum-volume bounding box of a point set in three dimensions. J. Algorithms 38:91--109, 2001.

Digital Library

[10]

M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer-Verlag, Heidelberg, 1997.

Digital Library

[11]

H. Breu, J. Gil, D. Kirkpatrick, and M. Werman. Linear time Euclidean distance transform algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17:529-533, 1995.

Digital Library

[12]

E. M. Bronshteyn and L. D. Ivanov. The approximation of convex sets by polyhedra. Siberian Math. J., 16:852--853, 1976.

[13]

T. M. Chan. Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus. Int. J. Comput. Geom. Appl., 12:67--85, 2002.

[14]

R. M. Dudley. Metric entropy of some classes of sets with differentiable boundaries. J. Approx. Theory, 10:227--236, 1974.

[15]

C. A. Duncan, M. T. Goodrich, and E. A. Ramos. Efficient approximation and optimization algorithms for computational metrology. In Proc. 8th ACM-SIAM Sympos. Discrete Algorithms pages 121--130, 1997.

Digital Library

[16]

J. Feigenbaum, S. Kannan, and J. Zhang. Computing diameter in the streaming and sliding-window models. Technical report YALEU/DCS/TR--1245, Yale University, 2002. Algorithmica, to appear.

[17]

S. Har-Peled. A practical approach for computing the diameter of a point-set. In Proc. 17th ACM Sympos. Comput. Geom., pages 177--186, 2001.

Digital Library

[18]

S. Har-Peled. A replacement for Voronoi diagrams of near linear size. In Proc. 42nd IEEE Sympos. Found. Comput. Sci., pages 94--103, 2001.

Digital Library

[19]

S. Har-Peled and K. Varadarajan. High-dimensional shape fitting in linear time. In Proc. 19th ACM Sympos. Comput. Geom., pages 39--47, 2003.

Digital Library

[20]

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

Digital Library

[21]

M. Henzinger, P. Raghavan, and S. Rajagopalan. Computing on data streams. Technical Note 1998--011, Digital Systems Research Center, Palo Alto, CA, 1998.

[22]

J. Hershberger and S. Suri. Convex hulls and related problems in data streams. ACM SIGMOD/PODS Workshop on Management and Processing of Data Streams (MPDS), http://www.research.att.com/-conf/mpds2003/schedule/, 2003.

[23]

R. Janardan. On maintaining the width and diameter of a planar point-set online. Int. J. Comput. Geom. Appl., 3:331--344, 1993.

[24]

G. Malandain and J.-D. Boissonnat. Computing the diameter of a point set. Int. J. Comput. Geom. Appl., 12:489--510, 2002.

[25]

S. Muthukrishnan. Data streams: algorithms and applications. http://www.cs.rutgers.edu/~muthu/, 2003.

[26]

G. Rote, C. Schwarz, and J. Snoeyink. Maintaining the approximate width of a set of points in the plane. In Proc. 5th Canad. Conf. Comput. Geom., pages 258--263, 1993.

[27]

J. O'Rourke. Finding minimal enclosing boxes. Internat. J. Comput. Info. Sci., 14:183--199, 1986.

[28]

O. Schwarzkopf. Parallel computation of distance transforms. Algorithmica, 6:685--697, 1991.

Digital Library

Cited By

Cohen-Addad VSaulpic DSchwiegelshohn C(2023)Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00066(1105-1130)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00066
Verma D(2022)Inference for Trustworthy Machine Intelligence: Challenges and Solutions2022 IEEE 4th International Conference on Cognitive Machine Intelligence (CogMI)10.1109/CogMI56440.2022.00014(27-34)Online publication date: Dec-2022
https://doi.org/10.1109/CogMI56440.2022.00014
Heusinger MSchleif F(2021)Classification in Non-stationary Environments Using Coresets over Sliding WindowsAdvances in Computational Intelligence10.1007/978-3-030-85030-2_11(126-137)Online publication date: 21-Aug-2021
https://doi.org/10.1007/978-3-030-85030-2_11
Show More Cited By

Index Terms

Faster core-set constructions and data stream algorithms in fixed dimensions
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Faster core-set constructions and data-stream algorithms in fixed dimensions

We speed up previous (1+@e)-factor approximation algorithms for a number of geometric optimization problems in fixed dimensions: diameter, width, minimum-radius enclosing cylinder, minimum-width enclosing annulus, minimum-width enclosing cylindrical ...
An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions

We present a new streaming algorithm for maintaining an ź-kernel of a point set in źd using O((1/ź(dź1)/2)logź(1/ź)) space. The space used by our algorithm is optimal up to a small logarithmic factor. This significantly improves (for any fixed dimension ...
A near-optimal algorithm for estimating the entropy of a stream

We describe a simple algorithm for approximating the empirical entropy of a stream of m values up to a multiplicative factor of (1+ϵ) using a single pass, O(ϵ⁻² log (δ⁻¹) log m) words of space, and O(log ϵ⁻¹ + log log δ⁻¹ + log log m) processing time ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '04: Proceedings of the twentieth annual symposium on Computational geometry

June 2004

468 pages

ISBN:1581138857

DOI:10.1145/997817

Conference Chairs:
Jack Snoeyink
UNC Chapel Hill
,
Jean-Daniel Boissonnat
INRIA Sophia Antipolis

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 June 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG04

Sponsor:

SoCG04: Annual ACM Symposium on Computational Geometry 2004

June 8 - 11, 2004

New York, Brooklyn, USA

Acceptance Rates

SCG '04 Paper Acceptance Rate 49 of 147 submissions, 33%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
624
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)1

Reflects downloads up to 15 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cohen-Addad VSaulpic DSchwiegelshohn C(2023)Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00066(1105-1130)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00066
Verma D(2022)Inference for Trustworthy Machine Intelligence: Challenges and Solutions2022 IEEE 4th International Conference on Cognitive Machine Intelligence (CogMI)10.1109/CogMI56440.2022.00014(27-34)Online publication date: Dec-2022
https://doi.org/10.1109/CogMI56440.2022.00014
Heusinger MSchleif F(2021)Classification in Non-stationary Environments Using Coresets over Sliding WindowsAdvances in Computational Intelligence10.1007/978-3-030-85030-2_11(126-137)Online publication date: 21-Aug-2021
https://doi.org/10.1007/978-3-030-85030-2_11
Heusinger MSchleif F(2020)Reactive Concept Drift Detection Using Coresets Over Sliding Windows2020 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI47803.2020.9308521(1350-1355)Online publication date: 1-Dec-2020
https://doi.org/10.1109/SSCI47803.2020.9308521
Braverman VFrahling GLang HSohler CYang L(2017)Clustering high dimensional dynamic data streamsProceedings of the 34th International Conference on Machine Learning - Volume 7010.5555/3305381.3305441(576-585)Online publication date: 6-Aug-2017
https://dl.acm.org/doi/10.5555/3305381.3305441
Huang LLi JKlein P(2017)Stochastic k-center and j-flat-center problemsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039694(110-129)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039694
Millman DLove SChan TSnoeyink J(2012)Computing the Nearest Neighbor Transform Exactly with Only Double PrecisionProceedings of the 2012 Ninth International Symposium on Voronoi Diagrams in Science and Engineering10.1109/ISVD.2012.13(66-74)Online publication date: 27-Jun-2012
https://dl.acm.org/doi/10.1109/ISVD.2012.13
Arkin EEfrat AHart GKostitsyna IKröller AMitchell JPolishchuk V(2012)Scandinavian thins on top of cakeProceedings of the 6th international conference on Fun with Algorithms10.1007/978-3-642-30347-0_5(16-27)Online publication date: 4-Jun-2012
https://dl.acm.org/doi/10.1007/978-3-642-30347-0_5
Sadjad BZsoldos Z(2011)Toward a Robust Search Method for the Protein-Drug Docking ProblemIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2010.708:4(1120-1133)Online publication date: 1-Jul-2011
https://dl.acm.org/doi/10.1109/TCBB.2010.70
Augustine JEppstein DWortman K(2010)Approximate weighted farthest neighbors and minimum dilation starsProceedings of the 16th annual international conference on Computing and combinatorics10.5555/1886811.1886826(90-99)Online publication date: 19-Jul-2010
https://dl.acm.org/doi/10.5555/1886811.1886826
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten