Fat Polygonal Partitions with Applications to Visualization and Embeddings

Details Fat Polygonal Partitions with Applications to Visualization and Embeddings Fat Polygonal Partitions with Applications to Visualization and Embeddings

2010-09-09

arxiv.org/abs/1009.1866v1

Computer Science

Computational Geometry

Scientific paper

Let T be a rooted and weighted tree, where the weight of any node is equal to the sum of the weights of its children. The popular Treemap algorithm visualizes such a tree as a hierarchical partition of a square into rectangles, where the area of the rectangle corresponding to any node in T is equal to the weight of that node. The aspect ratio of the rectangles in such a rectangular partition necessarily depends on the weights and can become arbitrarily high. We introduce a new hierarchical partition scheme, called a polygonal partition, which uses convex polygons rather than just rectangles. We present two methods for constructing polygonal partitions, both having guarantees on the worst-case aspect ratio of the constructed polygons; in particular, both methods guarantee a bound on the aspect ratio that is independent of the weights of the nodes. We also consider rectangular partitions with slack, where the areas of the rectangles may differ slightly from the weights of the corresponding nodes. We show that this makes it possible to obtain partitions with constant aspect ratio. This result generalizes to hyper-rectangular partitions in R^d. We use these partitions with slack for embedding ultrametrics into d-dimensional Euclidean space: we give a polylog(Delta)-approximation algorithm for embedding n-point ultrametrics into R^d with minimum distortion, where Delta denotes the spread of the metric. The previously best-known approximation ratio for this problem was polynomial in n. This is the first algorithm for embedding a non-trivial family of weighted-graph metrics into a space of constant dimension that achieves polylogarithmic approximation ratio.

Affiliated with

Also associated with

No associations

Rating

Fat Polygonal Partitions with Applications to Visualization and Embeddings 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 Fat Polygonal Partitions with Applications to Visualization and Embeddings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fat Polygonal Partitions with Applications to Visualization and Embeddings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-560043