Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants Decomposition

Details Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants Decomposition Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants Decomposition

2006-04-09

arxiv.org/abs/cs/0604034v2

ACM Trans. Algorithms 5(3): 29, 2009

Computer Science

Computational Geometry

22 pages, 14 figures. This version replaces the proof of what is now Lemma 5.2, as the previous proof was erroneous

Scientific paper

10.1145/1541885.1541890

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.

Affiliated with

Also associated with

No associations

Rating

Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants Decomposition does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants Decomposition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants Decomposition will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-267675