Re: Voronoi applet?
scot@flume.cs.dartmouth.edu
Mon, 23 Dec 1996 13:18:55 -0500 (EST)
> Chuck Biehl wrote:
> > 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.
>
> This is great -- questioning the very definitions and axioms on which
> the theory is built! How about getting students involved in the debate?
> They might come up with a lot of creative situations where something
> vaguely like VD is useful, but where standard VD won't apply.
>
> I don't want to taint the discussion too much...but before shutting up I
> will offer one "thought experiment" relating to your concept of steadily
> expanding spheres/circles of influence. Consider 2 points, and make
> point A's circle of influence expand ever-so-slowly while point B's
> blasts out like an explosion. By the time point A's circle is barely
> visible, point B's circle will have already blasted past A and be about
> to hit the moon.
>
> As you can see, the region that point A has any chance of influencing
> can be no more than some tiny blob around A. The exact shape of this
> blob may not be obvious, but what is clear from this experiment is that
> the boundary of the region cannot be a straight line! (If you don't
> like the results of this experiment, how should its implicit assumptions
> about the meaning of "expanding spheres of influence" be changed?)
There is a fair amount known about these sorts of variations, but
there are still interesting open questions. As I think Chuck pointed
out, in the case mentioned above the boundary between A and B's regions
will be a circle containing A (but not centered on it). This is called
a "multiplicatively weighted" Voronoi diagram. As Chuck points out in
another message, the regions need not be connected. If you really are
simulating crystal growth by crystals the start at the same time but grow
at different rates disconnected regions of course make no sense. Barry
Schaudt, a student of mine, wrote his thesis on these "Crystal Growth
Voronoi Diagrams". For just two sites the boundary starts as the same
circle that it would be in the multiplicatively weighted diagram, but
beyond the point where the line from the heavier site to the boundary
is tangent to the boundary you get logarithmic spirals! With more
sites you can get even more complicated curves for the boundary.
There are also "additively weighted" Voronoi diagrams where the
boundaries are branches of hyperbolas. It is a fun area to explore.
Scot