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 USAhmueller@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