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: 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
• 2: 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
• 3: 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]
• 4: 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]
• 5: 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
• 6: 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]
• 7: K. L. Clarkson. Fast algorithms for the all nearest neighbors problem. Proc. 24th IEEE Symp. Foundations of Computer Science (FOCS 1983), pp. 226--232, 1983.
• 8: Sanjoy Dasgupta, Performance Guarantees for Hierarchical Clustering, Proceedings of the 15th Annual Conference on Computational Learning Theory, p.351-363, July 08-10, 2002
• 9: D. Eppstein. Approximating the minimum weight Steiner triangulation. Discrete & Computational Geometry 11(2):163--191, 1994.
• 10: 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]
• 11: 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]
• 12: É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]
• 13: 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]
• 14: 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
• 15: S. C. Johnson. Hierarchical clustering schemes. Psychometrika 32(3):241--254, 1967.
• 16: 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]
• 17: 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]
• 18: S.-H. Poon and S. Thite. Pants decomposition of the punctured plane. ACM Computing Research Repository, arXiv:cs.CG/0602080.
• 19: Jim Ruppert, A Delaunay refinement algorithm for quality 2-dimensional mesh generation, Journal of Algorithms, v.18 n.3, p.548-585, May 1995
• 20: N. Saitou and M. Nei. The neighbor-joining method: a new method for reconstructing phylogenetic trees. Molecular Biology and Evolution 4(4):406--425, 1987.
• 21: J. Zupan. Clustering of Large Data Sets. Chemometrics Research Studies Ser. Research Studies Press, Chichester, 1982.