January 1999 Programmer's Challenge

Sphere Packing

Mail solutions to: progchallenge@mactech.com
Due Date: 11:59pm ET, Sunday, 3 January 1999

This month we’re going to help you recover from the clutter that might result from the holiday season. Imagine that your post-holiday household is filled with gifts, all of which have to be put somewhere. Imagine further that those gifts include sports equipment given to your children, or parents, or siblings, or grandchildren, as the case may be. And finally, imagine that the sports equipment includes a collection of balls of various sizes — basketballs, baseballs, soccer balls, beach balls, etc. (OK, if I’ve stretched your imagination to the breaking point, think of some other reason you might have a large collection of spherical objects.) We’ve got to find somewhere to store all of those balls, and space is at a premium. Fortunately, we also have a very large collection of boxes of various sizes, so many, in fact, that you can count on finding a box of the exact size that you might need. In keeping with our desire for a few less difficult problems, your Challenge is to pack the balls into the smallest box possible, so that we can store them efficiently.

The prototype for the code you should write is:

#if defined(__cplusplus)
extern "C" {
#endif

typedef struct Position {
  double coordinate[3];    /* coordinate[0]==X position, [1]==Y, [2]==Z */
} Position;

void PackSpheres(
  long numSpheres,         /* input: number of spheres to pack */
  double radius[],         /* input: radius of each of numSpheres spheres */
  Position location[]      /* output: location of center of each sphere */
);

#if defined (__cplusplus)
}
#endif