Squarepants in a tree: Sum of subtree clustering and hyperbolic pants decomposition

ABSTRACT

We provide efficient constant-factor approximation algorithms for the problems of finding a hierarchical clustering of a point set in any metric space, minimizing the sum of minimimum spanning tree lengths within each cluster, and in the hyperbolic or Euclidean planes, minimizing the sum of cluster perimeters. Our algorithms for the hyperbolic and Euclidean planes can also be used to provide a pants decomposition, that is, a set of disjoint simple closed curves partitioning the plane minus the input points into subsets with exactly three boundary components, with approximately minimum total length. In the Euclidean case, these curves are squares; in the hyperbolic case, they combine our Euclidean square pants decomposition with our tree clustering method for general metric spaces.

REFERENCES

• 1: Pankaj K. Agarwal , Cecilia M. Procopiuc, Approximation algorithms for projective clustering, Journal of Algorithms, v.46 n.2, p.115-139, February 2003 [doi>10.1016/S0196-6774(02)00295-X]
• 2: Pankaj K. Agarwal , Cecilia M. Procopiuc , Kasturi R. Varadarajan, A (1 + ɛ)-approximation algorithm for 2-line-center, Computational Geometry: Theory and Applications, v.26 n.2, p.119-128, October 2003 [doi>10.1016/S0925-7721(03)00017-8]
• 3: Stephen Alstrup , Jacob Holm , Mikkel Thorup, Maintaining Center and Median in Dynamic Trees, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.46-56, July 05-07, 2000
• 4: Srinivas Aluru , Fatih E. Sevilgen, Dynamic Compressed Hypertoctrees with Application to the N-Body Problem, Proceedings of the 19th Conference on Foundations of Software Technology and Theoretical Computer Science, p.21-33, December 13-15, 1999
• 5: Nina Amenta , Marshall Bern , David Eppstein, The crust and the &Bgr;-Skeleton: combinatorial curve reconstruction, Graphical Models and Image Processing, v.60 n.2, p.125-135, March 1, 1998 [doi>10.1006/gmip.1998.0465]
• 6: Jon Louis Bentley , Daniel D. Sleator , Robert E. Tarjan , Victor K. Wei, A locally adaptive data compression scheme, Communications of the ACM, v.29 n.4, p.320-330, April 1986 [doi>10.1145/5684.5688]
• 7: Marshall Bern, Approximate closest-point queries in high dimensions, Information Processing Letters, v.45 n.2, p.95-99, Feb. 26, 1993 [doi>10.1016/0020-0190(93)90222-U]
• 8: Marshall W. Bern , David Eppstein , Shang-Hua Teng, Parallel Construction of Quadtrees and Quality Triangulations, Proceedings of the Third Workshop on Algorithms and Data Structures, p.188-199, August 11-13, 1993
• 9: Blundo, C., and de Prisco, R. 1996. New bounds on the expected length of one-to-one codes. IEEE Trans. Inf. Theory IT-42, 246--250.
• 10: Allan Borodin , Rafail Ostrovsky , Yuval Rabani, Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces, Machine Learning, v.56 n.1-3, p.153-167 [doi>10.1023/B:MACH.0000033118.09057.80]
• 11: Kenneth L. Clarkson, Fast algorithms for the all nearest neighbors problem, Proceedings of the 24th Annual Symposium on Foundations of Computer Science, p.226-232, November 07-09, 1983 [doi>10.1109/SFCS.1983.16]
• 12: Sanjoy Dasgupta, Performance Guarantees for Hierarchical Clustering, Proceedings of the 15th Annual Conference on Computational Learning Theory, p.351-363, July 08-10, 2002
• 13: Peter Elias, Interval and recency rank source coding: two on-line adaptive variable-length schemes, IEEE Transactions on Information Theory, v.33 n.1, p.3-10, January 2, 1987 [doi>10.1109/TIT.1987.1057251]
• 14: Eppstein, D. 1994. Approximating the minimum weight Steiner triangulation. Discrete Comput. Geom. 11, 2, 163--191.
• 15: David Eppstein, Fast hierarchical clustering and other applications of dynamic closest pairs, Journal of Experimental Algorithmics (JEA), 5, p.1-es, 2000 [doi>10.1145/351827.351829]
• 16: David Eppstein , Michael T. Goodrich , Jonathan Z. Sun, The skip quadtree: a simple dynamic data structure for multidimensional data, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064138]
• 17: Éric Colin de Verdière , Jeff Erickson, Tightening non-simple paths and cycles on surfaces, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.192-201, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109580]
• 18: Tomás Feder , Daniel Greene, Optimal algorithms for approximate clustering, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.434-444, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62255]
• 19: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 20: Johnson, S. C. 1967. Hierarchical clustering schemes. Psychometrika 32, 3, 241--254.
• 21: David G. Kirkpatrick , Pavol Hell, On the completeness of a generalized matching problem, Proceedings of the tenth annual ACM symposium on Theory of computing, p.240-245, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804353]
• 22: Robert Krauthgamer , James R. Lee, Algorithms on negatively curved spaces, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.119-132, October 21-24, 2006 [doi>10.1109/FOCS.2006.9]
• 23: Leung-Yan-Cheong, S. K., and Cover, T. M. 1978. Some equivalences between Shannon entropy and Kolmogorov complexity. IEEE Trans. Inf. Theory IT-24, 331--338.
• 24: Poon, S.-H., and Thite, S. 2006. Pants decomposition of the punctured plane. ACM Computing Research Repository, cs.CG/0602080.
• 25: Jim Ruppert, A Delaunay refinement algorithm for quality 2-dimensional mesh generation, Journal of Algorithms, v.18 n.3, p.548-585, May 1995
• 26: Saitou, N., and Nei, M. 1987. The neighbor-joining method: A new method for reconstructing phylogenetic trees. Molecular Biol. Evol. 4, 4, 406--425.
• 27: Shannon, C. E. 1948. A mathematical theory of communication. Bell Syst. Tech. J. 27, 379--423.
• 28: Teufel, E. 1991. A generalization of the isoperimetric inequality in the hyperbolic plane. Archiv der Mathematik 57, 5, 508--513.
• 29: Wyner, A. D. 1972. An upper bound on the entropy series. Inf. Contr. 20, 176--181.
• 30: Zupan, J. 1982. Clustering of Large Data Sets. Chemometrics Research Studies Series. Research Studies Press, Chichester.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
Hierarchical clustering, approximation algorithm, hyperbolic geometry, minimum spanning tree, pants decomposition, sum of cluster sizes