Sariel Har-Peled
ABSTRACT
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 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 furthest nearest neighbor, k-center clustering, smallest disk enclosing k points, k-th largest distance, k-th smallest m-nearest neighbor distance, k-th 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. R. Varadarajan.hrefhttp://cs.uiuc.edu/~sariel/papers/01/fitting/Approximating extent measures of points. J. Assoc. Comput. Mach., 51(4):606--635, 2004. Google Scholar
Digital Library
- P. K. Agarwal, S. Har-Peled, and K. Varadarajan. Geometric approximation via coresets. In J. E. Goodman, J. Pach, and E. Welzl, editors, Combinatorial and Computational Geometry, Math. Sci. Research Inst. Pub. Cambridge, 2005.Google Scholar
- G. Aggarwal, R. Panigrahy, T. Feder, D. Thomas, K. Kenthapadi, S. Khuller, and A. Zhu. Achieving anonymity via clustering. ACM Trans. Algo., 6(3), 2010. Google ScholarDigital Library
- P. K. Agarwal, M. Sharir, and S. Toledo. Applications of parametric searching in geometric optimization. J. Algorithms, 17:292--318, 1994. Google ScholarDigital Library
- S. Bespamyatnikh and M. Segal. Fast algorithms for approximating distances. Algorithmica, 33(2):263--269, 2002.Google ScholarDigital Library
- K. L. Clarkson. Fast algorithms for the all nearest neighbors problem. In Proc. 24th Annu. IEEE Sympos. Found. Comput. Sci., pages 226--232, 1983. Google ScholarDigital Library
- A. Driemel, S. Har-Peled, and C. Wenk. Approximating the Fréchet distance for realistic curves in near linear time. Discrete Comput. Geom., 48:94--127, 2012. Google ScholarDigital Library
- H. ElGindy, H. Everett, and G. Toussaint. Slicing an ear using prune-and-search. Pattern Recogn. Lett., 14(9):719--722, 1993. Google ScholarDigital Library
- A. Ene, B. Raichel, and S. Har-Peled. Fast clustering with lower bounds: No customer too far, no shop too small. In submission. http://valis.cs.uiuc.edu/~sariel/papers/12/lbc/, 2012.Google Scholar
- J. Erickson.hrefhttp://compgeom.cs.uiuc.edu/~jeffe/pubs/relative.htmlOn the relative complexities of some geometric problems. In Proc. 7th Canad. Conf. Comput. Geom., pages 85--90, 1995.Google Scholar
- G. N. Frederickson and D. B. Johnson. Generalized selection and ranking: Sorted matrices. SIAM J. Comput., 13:14--30, 1984. Google ScholarDigital Library
- T. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci., 38:293--306, 1985.Google ScholarCross Ref
- M. Golin, R. Raman, C. Schwarz, and M. Smid. Simple randomized algorithms for closest pair problems. Nordic J. Comput., 2:3--27, 1995. Google ScholarDigital Library
- S. Har-Peled.hrefhttp://cs.uiuc.edu/~sariel/research/papers/01/cluster/Clustering motion. In Proc. 42nd Annu. IEEE Sympos. Found. Comput. Sci., pages 84--93, 2001. Google ScholarDigital Library
- S. Har-Peled.hrefhttp://cs.uiuc.edu/~sariel/research/papers/01/cluster/Clustering motion. Discrete Comput. Geom., 31(4):545--565, 2004. Google ScholarDigital Library
- S. Har-Peled.hrefhttp://cs.uiuc.edu/~sariel/papers/02/2slab/No coreset, no cry. In Proc. 24th Conf. Found. Soft. Tech. Theoret. Comput. Sci., 2004. Google ScholarDigital Library
- S. Har-Peled and A. Kushal.hrefhttp://cs.uiuc.edu/~sariel/papers/04/small_coreset/Smaller coresets for k-median and k-means clustering. In Proc. 21st Annu. ACM Sympos. Comput. Geom., pages 126--134, 2005. Google ScholarDigital Library
- S. Har-Peled and S. Mazumdar.hrefhttp://cs.uiuc.edu/~sariel/research/papers/03/kcoreset/Coresets for k-means and k-median clustering and their applications. In Proc. 36th Annu. ACM Sympos. Theory Comput., pages 291--300, 2004. Google ScholarDigital Library
- S. Har-Peled and S. Mazumdar.hrefhttp://cs.uiuc.edu/~sariel/papers/03/min_disk/Fast algorithms for computing the smallest k-enclosing disc. Algorithmica, 41(3):147--157, 2005. Google ScholarDigital Library
- S. Har-Peled and M. Mendel. Fast construction of nets in low dimensional metrics, and their applications. SIAM J. Comput., 35(5):1148--1184, 2006. Google ScholarDigital Library
- S. Har-Peled and B. Raichel. The Fréchet distance revisited and extended. In Proc. 27th Annu. ACM Sympos. Comput. Geom., pages 448--457, 2011. Google ScholarDigital Library
- S. Har-Peled and B. Raichel.hrefhttp://cs.uiuc.edu/~sariel/papers/12/aggregate/Net and prune: A linear time algorithm for euclidean distance problems. Manuscript, 2012.Google Scholar
- R. Krauthgamer and J. R. Lee. Navigating nets: simple algorithms for proximity search. In Proc. 15th ACM-SIAM Sympos. Discrete Algorithms, pages 798--807. Society for Industrial and Applied Mathematics, 2004. Google ScholarDigital Library
- C.-Y. Lo, J. Matou\v sek, and W. L. Steiger. Algorithms for ham-sandwich cuts. Discrete Comput. Geom., 11:433--452, 1994.Google ScholarCross Ref
- N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms. J. Assoc. Comput. Mach., 30(4):852--865, 1983. Google ScholarDigital Library
- N. Megiddo. Linear programming in linear time when the dimension is fixed. J. Assoc. Comput. Mach., 31:114--127, 1984. Google ScholarDigital Library
- J. Matousek, M. Sharir, and E. Welzl. A subexponential bound for linear programming. Algorithmica, 16:498--516, 1996.Google ScholarCross Ref
- M. O. Rabin. Probabilistic algorithms. In J. F. Traub, editor, Algorithms and Complexity: New Directions and Recent Results, pages 21--39. Academic Press, 1976.Google Scholar
- J. Salowe. Parametric search. In J. E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter~37, pages 683--698. CRC Press LLC, Boca Raton, FL, 1997. Google ScholarDigital Library
- A. Schönhage. On the power of random access machines. In Proc. 6th Internat. Colloq. Automata Lang. Prog., volume~71 of Lecture Notes Comput. Sci., pages 520--529, 1979. Google ScholarDigital Library
- M. Smid. Closest-point problems in computational geometry. In Jörg-Rüdiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 877--935. Elsevier, 2000.Google ScholarCross Ref
- M. Sharir and E. Welzl. A combinatorial bound for linear programming and related problems. In Proc. 9th Sympos. Theoret. Aspects Comput. Sci., volume 577 of Lect. Notes in Comp. Sci., pages 569--579. Springer-Verlag, 1992. Google ScholarDigital Library
- R. van Oostrum and R. C. Veltkamp. Parametric search made practical. Comput. Geom. Theory Appl., 28(2--3):75--88, 2004. 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
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 ...
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