[comp.ai] The Dice face problem

efrethei@blackbird.afit.af.mil (Erik J. Fretheim) (08/21/90)

In trying to write a program I came across an interesting problem
which for lack of a better name I call the dice face problem.  It has
probably been solved somewhere, but I have been unable to find a good
solution.  The basic problem is this:

   Given a discrete two dimensional array of points (l by m) and a set
   of n objects, place the objects uniformly distributed on the array
   in such a manner that the distance from any given point on the array 
   to any one of the objects is minimized.  This is similar to deciding
   where the dots on a die should be placed, but they must be put in 
   descrete locations and the sides of the die may not be equilateral.

   some examples for a square:

   1     o           2    o  o    3  o       4  o    o    5   o   o
					 o                      o
                                     o          o    o        o    o
 
   and so on (not much for graphics but you get the idea i hope)

   anyway if you have the solution please send it email.  This is fairly
   easy to work out by hand for small numbers, but for massive ones it
   boggles the mind.

   thank you 

   erik
   efrethei@afit.af.mil

-- 
--
Erik J Fretheim
efrethei@afit.af.mil			AFIT/ENA Box 4151 (ATTN: CPT FRETHEIM)
(513)255-5276 AVN785-5276 		WPAFB, OH 45431  USA

hmueller@wfsc4.tamu.edu (Hal Mueller) (08/21/90)

If you consider the points as vertices in a graph, and define the
graph such that there exists an edge from your desired center
to every other vertex, then the spring embedding of that graph
may be what you want.  Spring embedding models the graph as
like-charged points connected by springs.

Some code for computing this is contained in Steve Skiena's
"Combinatorica" extensions for Mathematica.

--
Hal Mueller            hmueller@cssun.tamu.edu          n270ca@tamunix (Bitnet)
Graduate Student, Department of Computer Science
Research Assistant, Department of Wildlife and Fisheries Sciences
Texas A&M University, College Station, TX 77843