Tiling algorithms
To create a treemap, one must define a tiling algorithm, that is, a way to divide a region into sub-regions of specified areas. Ideally, a treemap algorithm would create regions that satisfy the following criteria: # A small aspect ratio—ideally close to one. Regions with a small aspect ratio (i.e, fat objects) are easier to perceive. # Preserve some sense of the ordering in the input data (ordered). # Change to reflect changes in the underlying data (high stability). Unfortunately, these properties have an inverse relationship. As the aspect ratio is optimized, the order of placement becomes less predictable. As the order becomes more stable, the aspect ratio is degraded.Rectangular treemaps
To date, fifteen primary rectangular treemap algorithms have been developed:Convex treemaps
Rectangular treemaps have the disadvantage that their aspect ratio might be arbitrarily high in the worst case. As a simple example, if the tree root has only two children, one with weight and one with weight , then the aspect ratio of the smaller child will be , which can be arbitrarily high. To cope with this problem, several algorithms have been proposed that use regions that are general convex polygons, not necessarily rectangular. Convex treemaps were developed in several steps, each step improved the upper bound on the aspect ratio. The bounds are given as a function of - the total number of nodes in the tree, and - the total depth of the tree. #Onak and Sidiropoulos proved an upper bound of . #De-Berg and Onak and Sidiropoulos improve the upper bound to , and prove a lower bound of . #De-Berg and Speckmann and van-der-Weele. Conference version: improve the upper bound to , matching the theoretical lower bound. (For the special case where the depth is 1, they present an algorithm that uses only four classes of 45-degree-polygons (rectangles, right-angled triangles, right-angled trapezoids and 45-degree pentagons), and guarantees an aspect ratio of at most 34/7.) The latter two algorithms operate in two steps (greatly simplified for clarity): # The original tree is converted to a binary tree: each node with more than two children is replaced by a sub-tree in which each node has exactly two children. # Each region representing a node (starting from the root) is divided to two, using a line that keeps the angles between edges as large as possible. It is possible to prove that, if all edges of a convex polygon are separated by an angle of at least , then its aspect ratio is . It is possible to ensure that, in a tree of depth , the angle is divided by a factor of at most , hence the aspect ratio guarantee.Orthoconvex treemaps
In convex treemaps, the aspect ratio cannot be constant - it grows with the depth of the tree. To attain a constant aspect-ratio, Orthoconvex treemaps can be used. There, all regions are orthoconvex rectilinear polygons with aspect ratio at most 64; and the leaves are either rectangles with aspect ratio at most 8, or L-shapes or S-shapes with aspect ratio at most 32. For the special case where the depth is 1, they present an algorithm that uses only rectangles and L-shapes, and the aspect ratio is at most ; the internal nodes use only rectangles with aspect ratio at most .Other treemaps
;Voronoi Treemaps:. based on Voronoi diagram calculations. The algorithm is iterative and does not give any upper bound on the aspect ratio. ;Jigsaw Treemaps.: based on the geometry of space-filling curves. They assume that the weights are integers and that their sum is a square number. The regions of the map are rectilinear polygons and highly non-ortho-convex. Their aspect ratio is guaranteed to be at most 4. ;GosperMaps:. based on the geometry of Gosper curves. It is ordered and stable, but has a very high aspect ratio.History
Area-based visualizations have existed for decades. For example, mosaic plots (also known as Marimekko diagrams) use rectangular tilings to show joint distributions (i.e., most commonly they are essentially stacked column plots where the columns are of different widths). The main distinguishing feature of a treemap, however, is the recursive construction that allows it to be extended to hierarchical data with any number of levels. This idea was invented by professor Ben Shneiderman at theSee also
* Disk space analyzer * Information visualization * List of countries by economic complexity, which includes a list of Products Exports Treemaps. * Marimekko Chart, a similar concept with one level of explicit hierarchy.References
External links