Sariel Har-Peled
Skip Abstract Section
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.
- 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.Google Scholar
- P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. 2004. Approximating extent measures of points. J. Assoc. Comput. Mach. 51, 4, 606--635. DOI:http://dx.doi.org/10.1145/1008731.1008736 Google ScholarDigital Library
- P. K. Agarwal, M. Sharir, and S. Toledo. 1994. Applications of parametric searching in geometric optimization. J. Algorithms 17, 292--318. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- B. Aronov and S. Har-Peled. 2008. On approximating the depth and related problems. SIAM J. Comput. 38, 3, 899--921. Google ScholarDigital Library
- S. Bespamyatnikh and M. Segal. 2002. Fast algorithms for approximating distances. Algorithmica 33, 2, 263--269.Google ScholarDigital Library
- 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. Google ScholarDigital Library
- T. M. Chan. 2008. Well-separated pair decomposition in linear time? Inform. Process. Lett. 107, 5 (2008), 138--141. DOI:http://dx.doi.org/10.1016/j.ipl.2008.02.008 Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.htmlGoogle ScholarDigital Library
- 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. Google ScholarDigital Library
- H. ElGindy, H. Everett, and G. Toussaint. 1993. Slicing an ear using prune-and-search. Pattern Recogn. Lett. 14, 9, 719--722. Google ScholarDigital Library
- 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/.Google Scholar
- 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/∼jeffe/pubs/relative.html.Google Scholar
- G. N. Frederickson and D. B. Johnson. 1984. Generalized selection and ranking: Sorted matrices. SIAM J. Comput. 13 (1984), 14--30.Google ScholarCross Ref
- M. Golin, R. Raman, C. Schwarz, and M. Smid. 1995. Simple randomized algorithms for closest pair problems. Nordic J. Comput. 2 (1995), 3--27. Google ScholarDigital Library
- T. Gonzalez. 1985. Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci. 38, 293--306.Google ScholarCross Ref
- S. Har-Peled. 2001. Clustering motion. In Proceedings of FOCS. IEEE, 84--93. http://sarielhp.org/p/01/cluster/. Google ScholarDigital Library
- S. Har-Peled. 2004a. Clustering motion. Discrete Comput. Geom. 31, 4 (2004), 545--565. http://cs.uiuc.edu/∼sariel/research/papers/01/cluster/. Google ScholarDigital Library
- S. Har-Peled. 2004b. No coreset, no cry. In Proceedings of FSTTCS. Springer, 324--335. http://cs.uiuc.edu/∼sariel/papers/02/2slab/. Google ScholarDigital Library
- S. Har-Peled. 2011. Geometric Approximation Algorithms. Mathematical Surveys and Monographs, Vol. 173. Amer. Math. Soc., Boston, MA, USA. Google ScholarDigital Library
- S. Har-Peled and A. Kushal. 2007. Smaller coresets for k-median and k-means clustering. Discrete Comput. Geom. 37, 1, 3--19. Google ScholarDigital Library
- 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/. Google ScholarDigital Library
- 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/. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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/. Google ScholarDigital Library
- 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/. Google ScholarDigital Library
- 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.Google Scholar
- S. Khuller and Y. Matias. 1995. A simple randomized sieve algorithm for the closest-pair problem. Inform. Comput. 118, 34--37. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- C.-Y. Lo, J. Matoušek, and W. L. Steiger. 1994. Algorithms for ham-sandwich cuts. Discrete Comput. Geom. 11, 433--452. Google ScholarDigital Library
- J. Matoušek, M. Sharir, and E. Welzl. 1996. A subexponential bound for linear programming. Algorithmica 16 (1996), 498--516.Google ScholarCross Ref
- N. Megiddo. 1983. Applying parallel computation algorithms in the design of serial algorithms. J. Assoc. Comput. Mach. 30, 4 (1983), 852--865. Google ScholarDigital Library
- N. Megiddo. 1984. Linear programming in linear time when the dimension is fixed. J. Assoc. Comput. Mach. 31 (1984), 114--127. Google ScholarDigital Library
- R. Motwani and P. Raghavan. 1995. Randomized Algorithms. Cambridge University Press, Cambridge, UK. http://us.cambridge.org/titles/catalogue.asp?isbn=0521474655. Google ScholarDigital Library
- K. Mulmuley. 1994. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ.Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- R. van Oostrum and R. C. Veltkamp. 2004. Parametric search made practical. Comput. Geom. Theory Appl. 28, 2--3, 75--88. Google ScholarDigital Library
Index Terms
- Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems
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 ComputingWe 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