Re: Voronoi applet?
Chuck Biehl (cbiehl@magnus1.com)
Sun, 22 Dec 1996 07:30:37 -0500
Paul Burchard wrote:
>
> Chuck Biehl wrote:
> > How easy would it be to create an applet for generating a voronoi
> > diagram based on the "spheres of influence" of the vertices
> > which expand at different but input-specified rates?
>
> This is a very interesting generalization! Keep in mind, though, that
> the resulting boundaries between regions will no longer be straight
> lines.
>
> In fact, the set of points defined by the condition that the ratio of
> their distances to two fixed points be a certain number -- is a circle.
> (In the familiar case where the ratio is 1, the circle is of infinite
> radius and therefore appears to be a straight line.) Figuring out the
> center and radius of the circle as a function of the distance ratio is a
> good exercise in coordinate geometry. Working out what all the possible
> 3-point diagrams look like is an even more nifty problem.
>
> Though I'm not an expert on Voronoi diagrams, I doubt that existing
> applets for standard Voronoi could be adapted to this generalized
> problem. The basic reason is that the "cell" of a point can now be
> disconnected [I think...try out the 4-point example with speed=1 points
> at (1,0) and (-1,0) and speed=2 points at (0,2) and (0,-6)]. This could
> have serious consequences for the efficiency and structure of the
> algorithm.
>
> Anyway, great discussion topic! Can anyone else suggest good exercises
> to attack this problem?
>
> PB
Actually, I had in mind that there would be straight Voronoi edges
which would be tangent to the point of contact of the two expanding
circles. This actually makes more sense in terms of the meaning of the
VD, I think.