[nscbjwok] variations on circle packing

find the smallest circle within which can be packed a given set of circles (discs) of possibly varied sizes.  this problem seems to be well studied, especially the problem of packing identical circles into various shapes.

pack a collection of packed circles into yet another circle, minimizing the size of the outer circle.  in general, the input is a tree specifying enclosure relationships, so we will call this tree packing.

pack circles onto the surface of a sphere, minimizing the size of the sphere.

tree pack circles into circles, then those circles onto the surface of a sphere.  the two phases of problem (corresponding to a tree of height 2) are not independent because the area available inside an intermediate circle depends on the size (curvature) of the sphere.

pack spheres (balls) onto the surface (hypersurface) of a 3-sphere.

pack circles onto spheres, those spheres onto 3-spheres (embedded in 4D), then those 3-spheres (3-sphere and its interior) onto 4-spheres (embedded in 5D), etc.  this is tree packing through higher dimensions.  the difficulties of curved space mentioned above persist, probably getting exponentially worse.

we can also extend down one dimension: pack arc segments onto the perimeter of a circle.  in flat space the 1D problem is trivial (the minimal circle has perimeter equal to the sum of the given segments), but it becomes more difficult in curved space: what is the perimeter of a circle drawn on the surface of a sphere?

pack given ellipses into an ellipse.  you have freedom to choose the eccentricity of the outer ellipse, but the goal is to minimize the size of the outer ellipse.  size probably means area.

tree pack ellipses into ellipses into ellipses.  the goal is to minimize the size of the outermost (root) ellipse.  this problem is difficult because minimizing the size of intermediate ellipses might not be globally optimal: it might be better to choose a larger-area intermediate ellipse which packs better into its enclosing ellipse.

tree pack ellipsoids through dimensions, analogous to hyperspheres above.  the 1D problem is to pack given line segments, which may be bent, onto the perimeter of an ellipse.  there is flexibility to choose the eccentricity of the ellipse.  there might be some hairiness in defining hyperellipsoids in curved space.  there's also a major problem of long thin ellipses with almost no area but large perimeter.  such ellipses can then be wrapped like a barber pole onto the surface of a long thin prolate ellipsoid with almost no volume, or maybe a pancake-like oblate ellipsoid with almost no volume, and so forth.

pack given squares onto the surface of a cube.  square patches may bend over edges but may not cover a vertex.  two ways to define the problem: squares be rotated to any orientation, or they need to remain aligned with the edges of the cube.  the latter is the more elegant (and simpler) problem.

tree pack rectangles and bricks (future post tfzwneso).  tree pack hypercubes through dimensions.