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
olsen@hpfcdq.HP.COM (John Olsen) (08/22/90)
efrethei@blackbird.afit.af.mil (Erik J. Fretheim) writes: > 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. If you remove the square grid and specify a desired distance between points, then it looks like it would degrade to a hexagonal grid for the larger numbers. Could your result be obtained by maximizing the distance between each point and it's neighbors as well as between the point and the edge? John M. Olsen, Graphics Technology Division (303)229-6746 olsen@hpfcjo.HP.COM, olsen@hpfcdq.HP.COM Hewlett-Packard, Mail Stop 73, 3404 E. Harmony Road, Ft Collins, CO 80525