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 of a parental hemisphere and the triple
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.
Bottom-up pass:
We compute a target surface area
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
, 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 at level p is straightforward.
, so
euclidean radius
would be
.
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
,
the hyperbolic radius of the parental hemisphere is
.
The parent-child relationship becomes
Figure 7: We find spherical coordinates and
for
placing a child hemisphere on the surface of a parent hemisphere with
radius
.
Top-down pass: We use the radius
of the parent hemisphere
to compute the remaining two spherical coordinates
and
, which specify the position of the child hemisphere at level
p+1. We compute
and
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
angle between child n and child n+1
on band j is the sum of the angles
and
, which depend on the radii
and
of
the children.
We need to derive the angle
given some r as in Figure
7. An angle
depends on
, the radius of
the spherical cap at
. When we use the euclidean radius
and the euclidean right-angle triangle
formula we find the euclidean angle
.
If we instead use the hyperbolic radius
and the hyperbolic right-angle triangle formula we find the hyperbolic
angle
We substitute and
to obtain our total:
If the cumulative angle
is greater than
, we drop down
to the next band j+1 and reset
to 0.
(The very first child is a singular case, since the band is
just a spherical cap.) The
angle between a child on one
band and the next depends on the radius
of the largest child in
band j and the radius
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 given some r, as in
the bottom of Figure 7. The euclidean angle
corresponding to r is simply
. We substitute the
hyperbolic formula for right-angle triangles to find
We substitute and
to obtain our total:
Armed with the triple , we can center the child
hemisphere in the appropriate spot on the parent hemisphere.