2-Site Distance Function
Voronoi Diagrams
(a JAVA demo)
Version 3.1b. ©Matthew Dickerson 1997,1998,1999 |
Applet by Matthew Dickerson.
This Java demo visualizes the Voronoi diagrams of some 2-site distance function
Voronoi diagrams studied recently in a collaborative research project with
Gill Barequet
and R.L.Scot Drysdale:
- G. Barequet, M.T. Dickerson, and R.L.S. Drysdale, 2-point site Voronoi
diagrams, Proc. 6th Workshop on Algorithms and Data Structures
m(WADS), Vancouver, British Columbia, Canada, Lecture Notes in Computer
Science, 1663, Springer-Verlag, pp. 219-230, August 1999. (postscript
available at Gill's website)
Directory:
Notes:
- A preliminary report of this work was presented at the Center for
Geometric Computing Workshop on Computational Geometry (WOCG) at Duke
University in October 1997.
- The background image is part of a 2-site Voronoi for the Difference
Distance Function defined below.
|
SHORT DESCRIPTION:
This applet allows the user to explore, via the Voronoi diagram, some
2nd-order distance functions. These are distance functions defined
from a point to a pair of points.
Implemented in this applet so far are:
- Several distance functions defined below.
- Nearest- and Farthest-Neighbor Voronoi diagrams (with or without edges).
- A special bisector diagram that shows the "half-plane"
between the site-pairs (0,1) and (2,3).
- Different dimensions of the drawing board.
- Different sizes for drawing the sites.
- Random points sets or Mouse input (up to 13 points).
|
DISTANCE
FUNCTIONS |
Let E(p,q) be the Euclidean distance from p to q.
Then our distance functions are defined as follows: |
SUM distance |
The SUM distance from x to (p,q) is defined as:
SUM(x,(p,q)) = E(x,p) + E(x,q).
NOTE: With the exception
of "singularities" at the input sites, the Voronoi diagram for
a set of sites for this function is identical to the Voronoi diagram for
the PRODUCT function defined by E(x,p)*E(x,q) |
DIFFERENCE distance |
The DIFF distance from x to (p,q) is defined as:
DIFF(x,(p,q)) = |(E(x,p)-E(x,q))|.
This distance ranges from 0 to E(p,q). |
AREA distance |
The AREA distance from x to (p,q) is defined as:
AREA(x,(p,q)) is the area of the triangle (x,p,q). |
PERIMETER distance |
PERIMETER distance from x to (p,q) is defined as:
PERIMETER(x,(p,q))=E(x,p)+E(x,q)+E(p,q)
( or equivalently the perimeter of the triangle (x,p,q).) |
SEGMENT distance |
SEGMENT distance from x to (p,q) is defined as the distance
from the point x to the (closest point on the) segment pq. |
LINE distance |
LINE distance from x to (p,q) is defined as the distance from
the point x to the line pq. |
CIRCUMCIRCLE distance |
CIRCUMCIRCLE distance from x to (p,q) is the radius of circumcircle
through points x,p,q.
NOTE: Though the distance
defined by the "area" of the circumcircle gives a different distance,
the Voronoi diagrams for the two functions is equivalent. |
CENTER ANGLE distance |
CENTER ANGLE distance from x to (p,q) is the angle
pxq.
This distance ranges from 0 to pi. |
MINIMUM SIDE ANGLE distance |
MINIMUM SIDE ANGLE distance from x to (p,q) is the minimum
of the two angles xpq and xqp.
This distance ranges from 0 to pi. |
TOUR distance |
The TOUR distance from x to (p,q) is defined as:
TOUR(x,(p,q)) = E(p,q)+min{E(x,q),E(x,p)}. |
ASPECT RATIO distance |
The ASPECT distance from x to (p,q) is defined as:
ASPECT(x,(p,q)) = min{E(x,q),E(x,p)}/max{E(x,q),E(x,p)}.
This distance ranges from 0 to 1.
Note: we defined the aspect ratio as the min/max relationship
of the two distances. Intuitively, it also makes sense to define it as the
max/min relationship. (In the sense that to get a "good"
aspect ratio, you would want to minimize the max/min function.) However
for the max/min function, the distance (p,(p,q)) or (q,(p,q)) is undefined.
Nonetheless, you can use this applet to compute the VD of the max/min version.
Just select the far neighbor diagram, since the near-neighbor VD of the
max/min is the same as the far-neighbor VD of the min/max. |