Fat Polygonal Partitions with Applications to Visualization and Embeddings
Nov 2, 2011
ABSTRACT:
We show how to construct a hierarchical partition of the Euclidean plane into convex polygons, each having small aspect ratio, and satisfying prespecified volume constraints. Such a partition gives a natural extension of the popular Treemap visualization method. Our proposed algorithms are not constrained in using only rectangles, and can achieve provably better guarantees on the aspect ratio of the constructed polygons. Under relaxed conditions, we also construct rectangular partitions of the Euclidean space of any dimension.
Apart from the application to visualization, we use these partitions to obtain improved approximation algorithms for embedding ultrametrics into bounded-dimension Euclidean spaces. This gives the first algorithm for embedding a non-trivial family of weighted graph metrics into a space of constant dimension that achieves a polylogarithmic approximation ratio.
Joint work with Mark de Berg and Anastasios Sidiropoulos.
We show how to construct a hierarchical partition of the Euclidean plane into convex polygons, each having small aspect ratio, and satisfying prespecified volume constraints. Such a partition gives a natural extension of the popular Treemap visualization method. Our proposed algorithms are not constrained in using only rectangles, and can achieve provably better guarantees on the aspect ratio of the constructed polygons. Under relaxed conditions, we also construct rectangular partitions of the Euclidean space of any dimension.
Apart from the application to visualization, we use these partitions to obtain improved approximation algorithms for embedding ultrametrics into bounded-dimension Euclidean spaces. This gives the first algorithm for embedding a non-trivial family of weighted graph metrics into a space of constant dimension that achieves a polylogarithmic approximation ratio.
Joint work with Mark de Berg and Anastasios Sidiropoulos.