Circular partitions with applications to visualization and embeddings

ABSTRACT

We introduce a hierarchical partitioning scheme of the Euclidean plane, called circular partitions. Such a partition consists of a hierarchy of convex polygons, each having small aspect ratio, and satisfying specified volume constraints. We apply these partitions to obtain a natural extension of the popular Treemap visualization method. Our proposed algorithm is not constrained in using only rectangles, and can achieve provably better guarantees on the aspect ratio of the constructed polygons.

Under relaxed conditions, we can also construct circular partitions in higher-dimensional spaces. We use these relaxed partitions to obtain improved approximation algorithms for embedding ultrametrics into d-dimensional Euclidean space. In particular, we give a polylog(Delta)-approximation algorithm for embedding n-point ultrametrics into R^d with minimum distortion (Delta denotes the spread of the metric). The previously best-known approximation ratio for this problem was polynomial in n [Badoiu et al. SoCG 2006]. 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.

REFERENCES

• 1: D. Avis and M. Deza. The cut cone, l1 embedability, complexity and multicommodity flows. Networks, 21:595--617, 1991.
• 2: Mihai Bǎdoiu , Julia Chuzhoy , Piotr Indyk , Anastasios Sidiropou, Embedding ultrametrics into low-dimensional spaces, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137886]
• 3: Michael Balzer , Oliver Deussen, Voronoi Treemaps, Proceedings of the Proceedings of the 2005 IEEE Symposium on Information Visualization, p.7, October 23-25, 2005 [doi>10.1109/INFOVIS.2005.40]
• 4: Michael Balzer , Oliver Deussen , Claus Lewerentz, Voronoi treemaps for the visualization of software metrics, Proceedings of the 2005 ACM symposium on Software visualization, May 14-15, 2005, St. Louis, Missouri [doi>10.1145/1056018.1056041]
• 5: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 6: Yair Bartal , Manor Mendel, Dimension reduction for ultrametrics, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 7: Benjamin B. Bederson , Ben Shneiderman , Martin Wattenberg, Ordered and quantum treemaps: Making effective use of 2D space to display hierarchies, ACM Transactions on Graphics (TOG), v.21 n.4, p.833-854, October 2002 [doi>10.1145/571647.571649]
• 8: Thomas Bladh , David A. Carr , Matjaz Kljun, The Effect of Animated Transitions on User Navigation in 3D Tree-Maps, Proceedings of the Ninth International Conference on Information Visualisation, p.297-305, July 06-08, 2005 [doi>10.1109/IV.2005.122]
• 9: T. Bladh, D. A. Carr, and J. Scholl. Extending tree-maps to three dimensions: A comparative study. In APCHI, pages 50--59, 2004.
• 10: D. M. Bruls, C. Huizing, and J. J. van Wijk. Squarified treemaps. In W. de Leeuw, R. van Liere (eds.), Data Visualization 2000, Proceedings of the joint Eurographics and IEEE TCVG Symposium on Visualization, pages 33--42. Springer, 2000.
• 11: Mihai Bǎdoiu , Julia Chuzhoy , Piotr Indyk , Anastasios Sidiropoulos, Low-distortion embeddings of general metrics into the line, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060624]
• 12: Mihai Bǎdoiu , Kedar Dhamdhere , Anupam Gupta , Yuri Rabinovich , Harald Räcke , R. Ravi , Anastasios Sidiropoulos, Approximation algorithms for low-distortion embeddings into low-dimensional spaces, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 13: M. Cary, A. Rudra, and A. Sabharwal. On the hardness of embeddings between two finite metrics. In ICALP, pages 1412--1423, 2005.
• 14: Jeff Edmonds, Embedding into l²∞ is easy embedding into l²∞ is NP-complete, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.522-531, January 07-09, 2007, New Orleans, Louisiana
• 15: A. Hall and C. H. Papadimitriou. Approximating the distortion. In APPROX-RANDOM, pages 111--122, 2005.
• 16: Liqun Jin , David C. Banks, TennisViewer: A Browser for Competition Trees, IEEE Computer Graphics and Applications, v.17 n.4, p.63-65, July 1997 [doi>10.1109/38.595272]
• 17: Brian Johnson , Ben Shneiderman, Tree-Maps: a space-filling approach to the visualization of hierarchical information structures, Proceedings of the 2nd conference on Visualization '91, October 22-25, 1991, San Diego, California
• 18: W.-A. Jungmeister and D. Turo. Adapting treemaps to stock portfolio visualization. Technical Report UMCP-CSD CS-TR-2996, College Park, Maryland 20742, U.S.A., 1992.
• 19: Claire Kenyon , Yuval Rabani , Alistair Sinclair, Low distortion maps between point sets, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007398]
• 20: James R. Lee , Assaf Naor , Yuval Peres, Trees and Markov convexity, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1028-1037, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109671]
• 21: N. Linial , E. London , Y. Rabinovich, The geometry of graphs and some of its algorithmic applications, Proceedings of the Proceedings 35th Annual Symposium on Foundations of Computer Science, p.577-591, November 20-22, 1994 [doi>10.1109/SFCS.1994.365733]
• 22: S. Malitz and J. Malitz. A bounded compactness theorem for l1-embeddings of metric spaces in the plane. In Discrete Comput. Geom., 8:373--385, 1992.
• 23: J. Matoušek and A. Sidiropoulos. On the computational near-optimality of random projection. Manuscript, 2008.
• 24: Christos Papadimitriou , Shmuel Safra, The complexity of low-distortion embeddings between point sets, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 25: J. Rekimoto and M. Green. The information cube: Using transparency in 3d information visualization. In Proceedings of the Third Annual Workshop on Information Technologies and Systems (WITS'93), pages 125--132, 1993.
• 26: B. Shneiderman. Treemaps for space-constrained visualization of hierarchies. Available at http://www.cs.umd.edu/hcil/treemaphistory/index.shtml.
• 27: Ben Shneiderman, Tree visualization with tree-maps: 2-d space-filling approach, ACM Transactions on Graphics (TOG), v.11 n.1, p.92-99, Jan. 1992 [doi>10.1145/102377.115768]
• 28: Ben Shneiderman , Martin Wattenberg, Ordered Treemap Layouts, Proceedings of the IEEE Symposium on Information Visualization 2001 (INFOVIS'01), p.73, October 22-23, 2001
• 29: John Stasko, An evaluation of space-filling information visualizations for depicting hierarchical structures, International Journal of Human-Computer Studies, v.53 n.5, p.663-694, Nov. 2000 [doi>10.1006/ijhc.2000.0420]
• 30: David Turo , Brian Johnson, Improving the visualization of hierarchies with treemaps: design issues and experimentation, Proceedings of the 3rd conference on Visualization '92, October 19-23, 1992, Boston, Massachusetts
• 31: Jarke J. Van Wijk , Huub van de Wetering, Cushion Treemaps: Visualization of Hierarchical Information, Proceedings of the 1999 IEEE Symposium on Information Visualization, p.73, October 24-29, 1999

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, embeddings, treemap, ultrametrics, visualization