 |
|
|
|
The Voronoi diagram under a smooth and strictly convex distance
function dC has similar properties as under the Euclidean
metric. If a convex distance function is not strictly convex, then the
bisector of two points is not necessarily a curve, it can contain a region.
This degenerated case can appear if the line through the two points is
parallel to an edge of the boundary of the convex set C. In this
case, the bisector contains a region between two
intersecting rays; then we consent to take only a ray in this region
as the bisector. In that way, a bisector is always a curve, and the Voronoi
diagram is a complete subdivision of the plane.
In this program we show a Voronoi diagram under a convex distance function dC, where C is a convex polygon. The convex polygon and the Voronoi diagram determined by this convex polygon are shown in the Convex Hull and in the Voronoi window,&nbs! respectively. Add (remove) points by pushing the left (right) mouse button. Drage points around with the letf button. The convex hull and the Voronoi diagram are maintained dynamically. Observe that the topological properties of the Voronoi diagram maintain, if the center of the convex polygon in the Convex Hull window is moved in the interior but not to close to the boundary of the convex hull.
Autorin: Lihong.Ma@fernuni-hagen.de
