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:

A quick description of the applet
Instructions
Distance functions (including 4 new DFs in Version 3)
Run the Program.
Run a version that allows text input and displays the coordinates of the input sites.

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.

INSTRUCTIONS

To use this program...

From the pull down menu, select the size of the drawing area. (Default is 100x100 pixels).
Create a point set either by mouse input or by random. (Because of color limitations, the program supports at most 13 points.)
Choose the desired distance function from the pull-down menu.
Choose the desired diagram from the rightmost pull-down menu. Choices are near-neighbor diagram, near-neighbor diagram with visible edges, far-neighbor diagram, far-neighbor diagram with edges, or a special bisector diagram that shows only the bisector (set of equidistance points) for the regions of point pairs (0,1) and (1,2).
Click on the DrawVD button.

WARNING: The run-time is O(A(c+n^2)) where n is the number of points, A is the size of the drawing area in pixels, and c is a large constant. In other words, for moderate point sets, the time is consumed by the drawing rather than the computation of minimum distance. On a 120MHz PowerMac, it takes 1/2 a minute to compute a 300x300 drawing, and the number of points doesn't matter much. To create a 700x700 drawing I leave the room and get lunch. On my 233MHz Pentium (and presumably on a 400MHz or faster anything) things are much faster and you can safely do 300x300 drawings in a couple seconds. Increasing n from 4 to 13 makes a small difference, but nothing like the quadratic time one would expect from an n^2 algorithm.

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.