next up previous
Next: Figures Up: H3: Laying Out Large Previous: References

Appendix A: Layout Derivation

The H3 layout method operates in two passes: in the bottom-up pass we find an approximate radius for each hemisphere and in the top-down pass we place children on the surface of their parent hemisphere. In this Appendix we present a detailed derivation of the radius tex2htm_wrap_inline612 of a parental hemisphere and the triple tex2htm_wrap_inline709 needed to place a child hemisphere on the surface of that parental hemisphere. For each step of the derivation, we show first the euclidean then the hyperbolic result.


tex2htm_wrap_inline616 Bottom-up pass: We compute a target surface area tex2htm_wrap_inline733 of a hemisphere at level p by summing the areas of the disks at the bottom of the child hemispheres at level p+1. This target surface area is only an approximation for three reasons. First, the surface area of a spherical cap is greater than the disk on which it lies. (We use the disk approximation since its area does not depend on the as yet unknown parental radius tex2htm_wrap_inline612 , which we would need to compute the area of the spherical cap.) Second, even an optimal circle packing of the disks of the sphere leaves uncovered gaps between the circles. Third, our circle packing is known to be suboptimal: circles may use less vertical space than their alloted band allows, and there may be unused horizontal space in the outermost band. These issues are discussed in more detail in Section 3.

All three reasons lead to an estimate which is less than the necessary area. We use an empirically derived area scaling factor to ensure that collisions do not occur. The other parameter in our implementation is the surface area alloted for hemispheres of leaf nodes. The layout would be too dense if the leaf nodes touched, so we generally specify a larger area than a hemisphere that would exactly fit around the geometric representation of a node. These two parameters control the density of the layout.

The euclidean derivation of the target hemisphere surface area tex2htm_wrap_inline741 at level p is straightforward. tex2htm_wrap_inline745 , so euclidean radius tex2htm_wrap_inline612 would be tex2htm_wrap_inline749 . The relationship between the parent and child hemispheres is


where DA is the area of the disk at the bottom of a child hemisphere and n is the number of children at level p+1.

When we use the hyperbolic area formula tex2htm_wrap_inline757 , the hyperbolic radius of the parental hemisphere is tex2htm_wrap_inline759 .

The parent-child relationship becomes



Figure 7: We find spherical coordinates tex2htm_wrap_inline608 and tex2htm_wrap_inline610 for placing a child hemisphere on the surface of a parent hemisphere with radius tex2htm_wrap_inline612 .

tex2htm_wrap_inline616 Top-down pass: We use the radius tex2htm_wrap_inline612 of the parent hemisphere to compute the remaining two spherical coordinates tex2htm_wrap_inline771 and tex2htm_wrap_inline773 , which specify the position of the child hemisphere at level p+1. We compute tex2htm_wrap_inline771 and tex2htm_wrap_inline773 cumulatively, starting from the pole at the top of the hemisphere. The children are laid out in concentric bands surrounding the pole at the top of the hemisphere. The total tex2htm_wrap_inline781 angle between child n and child n+1 on band j is the sum of the angles tex2htm_wrap_inline789 and tex2htm_wrap_inline791 , which depend on the radii tex2htm_wrap_inline793 and tex2htm_wrap_inline795 of the children. We need to derive the angle tex2htm_wrap_inline610 given some r as in Figure 7. An angle tex2htm_wrap_inline610 depends on tex2htm_wrap_inline803 , the radius of the spherical cap at tex2htm_wrap_inline771 . When we use the euclidean radius tex2htm_wrap_inline807 and the euclidean right-angle triangle formula we find the euclidean angle tex2htm_wrap_inline809 . If we instead use the hyperbolic radius tex2htm_wrap_inline811 and the hyperbolic right-angle triangle formula we find the hyperbolic angle


We substitute tex2htm_wrap_inline793 and tex2htm_wrap_inline795 to obtain our total:


If the cumulative angle tex2htm_wrap_inline817 is greater than tex2htm_wrap_inline819 , we drop down to the next band j+1 and reset tex2htm_wrap_inline823 to 0. (The very first child is a singular case, since the band is just a spherical cap.) The tex2htm_wrap_inline608 angle between a child on one band and the next depends on the radius tex2htm_wrap_inline827 of the largest child in band j and the radius tex2htm_wrap_inline831 of the largest child in band j+1. In our current circle packing approach, we know that the first child in each band will have the largest radius, since we lay out the children in descending sorted order.

We thus need to derive the angle tex2htm_wrap_inline608 given some r, as in the bottom of Figure 7. The euclidean angle tex2htm_wrap_inline771 corresponding to r is simply tex2htm_wrap_inline843 . We substitute the hyperbolic formula for right-angle triangles to find


We substitute tex2htm_wrap_inline827 and tex2htm_wrap_inline831 to obtain our total:


Armed with the triple tex2htm_wrap_inline849 , we can center the child hemisphere in the appropriate spot on the parent hemisphere.

next up previous
Next: Figures Up: H3: Laying Out Large Previous: References

Tamara Munzner Tue Jul 22 08:42:41 PDT 1997