research-article

Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems

Authors:

Sariel Har-Peled,

Benjamin RaichelAuthors Info & Claims

Journal of the ACM (JACM), Volume 62, Issue 6

Article No.: 44, Pages 1 - 35

https://doi.org/10.1145/2831230

Published: 10 December 2015 Publication History

Abstract

We provide a general framework for getting expected linear time constant factor approximations (and in many cases FPTAS's) to several well known problems in Computational Geometry, such as k-center clustering and farthest nearest neighbor. The new approach is robust to variations in the input problem, and yet it is simple, elegant, and practical. In particular, many of these well studied problems which fit easily into our framework, either previously had no linear time approximation algorithm, or required rather involved algorithms and analysis. A short list of the problems we consider include farthest nearest neighbor, k-center clustering, smallest disk enclosing k points, kth largest distance, kth smallest m-nearest neighbor distance, kth heaviest edge in the MST and other spanning forest type problems, problems involving upward closed set systems, and more. Finally, we show how to extend our framework such that the linear running time bound holds with high probability.

References

[1]

P. K. Agarwal, S. Har-Peled, and K. Varadarajan. 2005. Geometric approximation via coresets. In Combinatorial and Computational Geometry, J. E. Goodman, J. Pach, and E. Welzl (Eds.). Cambridge, New York.

[2]

P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. 2004. Approximating extent measures of points. J. Assoc. Comput. Mach. 51, 4, 606--635.

Digital Library

[3]

P. K. Agarwal, M. Sharir, and S. Toledo. 1994. Applications of parametric searching in geometric optimization. J. Algorithms 17, 292--318.

Digital Library

[4]

G. Aggarwal, R. Panigrahy, T. Feder, D. Thomas, K. Kenthapadi, S. Khuller, and A. Zhu. 2010. Achieving anonymity via clustering. ACM Trans. Algorithms 6, 3, Article 49, 19 pages.

Digital Library

[5]

B. Aronov and S. Har-Peled. 2008. On approximating the depth and related problems. SIAM J. Comput. 38, 3, 899--921.

Digital Library

[6]

S. Bespamyatnikh and M. Segal. 2002. Fast algorithms for approximating distances. Algorithmica 33, 2, 263--269.

Digital Library

[7]

P. B. Callahan and S. R. Kosaraju. 1995. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. Assoc. Comput. Mach. 42 (1995), 67--90.

Digital Library

[8]

T. M. Chan. 2008. Well-separated pair decomposition in linear time? Inform. Process. Lett. 107, 5 (2008), 138--141.

Digital Library

[9]

K. L. Clarkson. 1983. Fast algorithms for the all nearest neighbors problem. In Proc. 24th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS). IEEE, 226--232.

Digital Library

[10]

K. L. Clarkson. 1988. Applications of random sampling in computational geometry, II. In Proceedings of the 4th Annual Symposium on Computer Geometry. ACM, New York, 1--11.

Digital Library

[11]

K. L. Clarkson and P. W. Shor. 1989. Applications of random sampling in computational geometry, II. Discrete Comput. Geom. 4, 387--421. http://cm.bell-labs.com/who/clarkson/rs2m.html

Digital Library

[12]

A. Driemel, S. Har-Peled, and C. Wenk. 2012. Approximating the Fréchet distance for realistic curves in near linear time. Discrete Comput. Geom. 48 (2012), 94--127. Issue 1.

Digital Library

[13]

H. ElGindy, H. Everett, and G. Toussaint. 1993. Slicing an ear using prune-and-search. Pattern Recogn. Lett. 14, 9, 719--722.

Digital Library

[14]

A. Ene, B. Raichel, and S. Har-Peled. 2012. Fast clustering with lower bounds: No customer too far, no shop too small. In submission. http://sarielhp.org/papers/12/lbc/.

[15]

J. Erickson. 1995. On the relative complexities of some geometric problems. In Proceedings of the 7th Canadian Conference on Computer Geometry. Carleton University, Ottawa, Canada, 85--90. http://compgeom.cs.uiuc.edu/&sim;jeffe/pubs/relative.html.

[16]

G. N. Frederickson and D. B. Johnson. 1984. Generalized selection and ranking: Sorted matrices. SIAM J. Comput. 13 (1984), 14--30.

[17]

M. Golin, R. Raman, C. Schwarz, and M. Smid. 1995. Simple randomized algorithms for closest pair problems. Nordic J. Comput. 2 (1995), 3--27.

Digital Library

[18]

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

[19]

S. Har-Peled. 2001. Clustering motion. In Proceedings of FOCS. IEEE, 84--93. http://sarielhp.org/p/01/cluster/.

Digital Library

[20]

S. Har-Peled. 2004a. Clustering motion. Discrete Comput. Geom. 31, 4 (2004), 545--565. http://cs.uiuc.edu/&sim;sariel/research/papers/01/cluster/.

Digital Library

[21]

S. Har-Peled. 2004b. No coreset, no cry. In Proceedings of FSTTCS. Springer, 324--335. http://cs.uiuc.edu/&sim;sariel/papers/02/2slab/.

Digital Library

[22]

S. Har-Peled. 2011. Geometric Approximation Algorithms. Mathematical Surveys and Monographs, Vol. 173. Amer. Math. Soc., Boston, MA, USA.

Digital Library

[23]

S. Har-Peled and A. Kushal. 2007. Smaller coresets for k-median and k-means clustering. Discrete Comput. Geom. 37, 1, 3--19.

Digital Library

[24]

S. Har-Peled and S. Mazumdar. 2004. Coresets for k-median and k-means clustering and their applications. In Proceedings of STOC. ACM, 291--300. http://cs.uiuc.edu/simsariel/research/papers/03/kcoreset/.

Digital Library

[25]

S. Har-Peled and S. Mazumdar. 2005. Fast algorithms for computing the smallest k-enclosing disc. Algorithmica 41, 3 (2005), 147--157. http://cs.uiuc.edu/simsariel/papers/03/min_disk/.

Digital Library

[26]

S. Har-Peled and M. Mendel. 2006. Fast construction of nets in low dimensional metrics, and their applications. SIAM J. Comput. 35, 5 (2006), 1148--1184.

Digital Library

[27]

S. Har-Peled and B. Raichel. 2011. The Fréchet distance revisited and extended. In Proceedings of SoCG. ACM, New York, 448--457. http://sarielhp.org/papers/10/frechet3d/.

Digital Library

[28]

S. Har-Peled and B. Raichel. 2013. Net and Prune: A linear time algorithm for Euclidean distance problems. In Proceedings of STOC. ACM, New York, 605--614. http://cs.uiuc.edu/simsariel/papers/12/aggregate/.

Digital Library

[29]

S. Har-Peled and B. Raichel. 2014. Net and Prune: A linear time algorithm for Euclidean distance problems. CoRR abs/1409.7425 (2014). http://arxiv.org/abs/1409.7425.

[30]

S. Khuller and Y. Matias. 1995. A simple randomized sieve algorithm for the closest-pair problem. Inform. Comput. 118, 34--37.

Digital Library

[31]

R. Krauthgamer and J. R. Lee. 2004. Navigating nets: Simple algorithms for proximity search. In Proceedings of SODA. Society for Industrial and Applied Mathematics, Philadelphia, PA, 798--807.

Digital Library

[32]

C.-Y. Lo, J. Matoušek, and W. L. Steiger. 1994. Algorithms for ham-sandwich cuts. Discrete Comput. Geom. 11, 433--452.

Digital Library

[33]

J. Matoušek, M. Sharir, and E. Welzl. 1996. A subexponential bound for linear programming. Algorithmica 16 (1996), 498--516.

[34]

N. Megiddo. 1983. Applying parallel computation algorithms in the design of serial algorithms. J. Assoc. Comput. Mach. 30, 4 (1983), 852--865.

Digital Library

[35]

N. Megiddo. 1984. Linear programming in linear time when the dimension is fixed. J. Assoc. Comput. Mach. 31 (1984), 114--127.

Digital Library

[36]

R. Motwani and P. Raghavan. 1995. Randomized Algorithms. Cambridge University Press, Cambridge, UK. http://us.cambridge.org/titles/catalogue.asp?isbn=0521474655.

Digital Library

[37]

K. Mulmuley. 1994. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ.

[38]

M. O. Rabin. 1976. Probabilistic algorithms. In Algorithms and Complexity: New Directions and Recent Results, J. F. Traub (Ed.). Academic Press, Orlando, FL, USA, 21--39.

[39]

J. Salowe. 1997. Parametric search. In Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke (Eds.). CRC Press LLC, Boca Raton, FL, Chapter 37, 683--698.

Digital Library

[40]

A. Schönhage. 1979. On the power of random access machines. In Proc. 6th Internat. Colloq. Automata Lang. Prog. (Lecture Notes Comput. Sci.), Vol. 71. Springer-Verlag, London, UK, 520--529.

Digital Library

[41]

M. Sharir and E. Welzl. 1992. A combinatorial bound for linear programming and related problems. In Proceedings of the 9th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 577. Springer, 569--579.

Digital Library

[42]

M. Smid. 2000. Closest-point problems in computational geometry. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia (Eds.). Elsevier, Amsterdam, Netherlands, 877--935.

[43]

R. van Oostrum and R. C. Veltkamp. 2004. Parametric search made practical. Comput. Geom. Theory Appl. 28, 2--3, 75--88.

Digital Library

Cited By

Agarwal PEsmailpour AHu XSintos SYang J(2024)Computing A Well-Representative Summary of Conjunctive Query ResultsProceedings of the ACM on Management of Data10.1145/36958352:5(1-27)Online publication date: 7-Nov-2024
https://dl.acm.org/doi/10.1145/3695835
Fox EHuang HRaichel B(2024)Clustering with faulty centersComputational Geometry: Theory and Applications10.1016/j.comgeo.2023.102052117:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.comgeo.2023.102052
de Berg MBodlaender HKisfaludi-Bak SKolay S(2023)An ETH-Tight Exact Algorithm for Euclidean TSPSIAM Journal on Computing10.1137/22M146912252:3(740-760)Online publication date: 5-Jun-2023
https://doi.org/10.1137/22M1469122
Show More Cited By

Index Terms

Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Net and prune: a linear time algorithm for euclidean distance problems
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

We provide a general framework for getting linear time constant factor approximations (and in many cases FPTAS's) to a copious amount of well known and well studied problems in Computational Geometry, such as k-center clustering and furthest nearest ...
The smoothed complexity of edit distance

We initiate the study of the smoothed complexity of sequence alignment, by proposing a semi-random model of edit distance between two input strings, generated as follows: First, an adversary chooses two binary strings of length d and a longest common ...
Linear Time Algorithms for Exact Distance Transform

In 2003, Maurer et al. (IEEE Trans. Pattern Anal. Mach. Intell. 25:265---270, 2003) published a paper describing an algorithm that computes the exact distance transform in linear time (with respect to image size) for the rectangular binary images in the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 62, Issue 6

December 2015

304 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/2856350

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2015 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 December 2015

Accepted: 01 September 2015

Revised: 01 January 2015

Received: 01 September 2013

Published in JACM Volume 62, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

NSF AF awards CCF-0915984 and CCF-1217462

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
598
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)4

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Agarwal PEsmailpour AHu XSintos SYang J(2024)Computing A Well-Representative Summary of Conjunctive Query ResultsProceedings of the ACM on Management of Data10.1145/36958352:5(1-27)Online publication date: 7-Nov-2024
https://dl.acm.org/doi/10.1145/3695835
Fox EHuang HRaichel B(2024)Clustering with faulty centersComputational Geometry: Theory and Applications10.1016/j.comgeo.2023.102052117:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.comgeo.2023.102052
de Berg MBodlaender HKisfaludi-Bak SKolay S(2023)An ETH-Tight Exact Algorithm for Euclidean TSPSIAM Journal on Computing10.1137/22M146912252:3(740-760)Online publication date: 5-Jun-2023
https://doi.org/10.1137/22M1469122
Lu JTang JXing BTang X(2022)Stochastic Approximate Algorithms for Uncertain Constrained K-Means ProblemMathematics10.3390/math1001014410:1(144)Online publication date: 4-Jan-2022
https://doi.org/10.3390/math10010144
Cavaleiro MAlizadeh F(2022)A branch-and-bound method for the minimum k−enclosing ball problemOperations Research Letters10.1016/j.orl.2022.02.00750:3(274-280)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.orl.2022.02.007
Sun HZhu LGuo LLuo YDu DSun Y(2021)Understanding the different responses from the similarity between displacement and groundwater level time series in Beijing, ChinaNatural Hazards10.1007/s11069-021-05041-9111:1(1-18)Online publication date: 28-Sep-2021
https://doi.org/10.1007/s11069-021-05041-9
Avarikioti ZEmiris IKavouras LPsarros I(2020)High-Dimensional Approximate r-NetsAlgorithmica10.1007/s00453-019-00664-882:6(1675-1702)Online publication date: 1-Jun-2020
https://dl.acm.org/doi/10.1007/s00453-019-00664-8
Avarikioti GRyser AWang YWattenhofer R(2019)High dimensional clustering with r-netsProceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v33i01.33013207(3207-3214)Online publication date: 27-Jan-2019
https://dl.acm.org/doi/10.1609/aaai.v33i01.33013207
Feng QHu JHuang NWang J(2019)Improved PTAS for the constrained k-means problemJournal of Combinatorial Optimization10.1007/s10878-018-0340-437:4(1091-1110)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s10878-018-0340-4
Arafat NBasu DBressan S(2019)Topological Data Analysis with -net Induced Lazy Witness ComplexDatabase and Expert Systems Applications10.1007/978-3-030-27618-8_28(376-392)Online publication date: 26-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-030-27618-8_28
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents