Geometry Lab: Weighted farthest color Voronoi diagrams on trees and graphs

[German] [Sitemap] [About geometrylab.de]

Weighted farthest color Voronoi diagrams on trees and graphs

Given an undirected graph and a set of n sites with each site sitting on a specific position on one of the graph's edges, consider a situation where each of the n sites represents one of k different types of facilities, like schools, shopping malls, hospitals, etc. A person choosing a new residence might want to have one representative of each type as close by as possible.
This problem can be solved by means of the farthest color Voronoi diagram.

We differentiate between Voronoi diagrams (VD) and farthest color Voronoi diagrams (FCVD). In case the multiplicative weight of sites is of interest, we speak of weighted Voronoi diagrams (WVD) and weighted farthest color Voronoi diagrams (WFCVD).
We further distinguish between trees and graphs, because in the case of trees we can apply a less complex algorithm to compute the desired Voronoi diagram.
Altogether this leads to eight different algorithms that are used by our applets we present here.

More information on weighted farthest color Voronoi diagrams on trees and graphs, including complexity and computation deliberations, can be found in this paper:
WFCVD (PS, unzipped, 214K) WFCVD (PS, g-zipped, 71K)
WFCVD (PDF, unzipped, 545K) WFCVD (PDF, g-zipped, 163K)

How to use the applets

We have created two separate applets for simplification. VDApplet uses algorithms for normal Voronoi diagrams, FCVDApplet shows the farthest color variant. Both applets have an option to regard the weighted case, where each site's multiplicative weight is applied.

The graph editor of each applet allows to create a tree or graph by setting nodes and drawing edges between them. Sites can be set on every edge with a single click on the desired position. A right button click on any graph component opens a context menu that allows altering the component's properties and removing the whole component.
A right button click on editor's empty space opens the editor context menu. Some of its options are grayed out because they can only be used if the editor is in application mode (access to user's file system). The menu allows creating a new graph (note: only create an undirected graph to ensure proper Voronoi computation) and changing default values for components' properties. The actual default value is applied to all components that are drawed after the default value is set.

Below the editor pane is a checkbox that switches between weighted and unweighted Voronoi diagrams. At the right one gets a short information about the currently drawed graph and the algorithm used to compute the Voronoi diagram. Note that the algorithms switch automatically according to the graph's layout; if the actual graph is a tree, the according tree algorithm is used rather than the more complex graph algorithm.

At the bottom there are algorithm-specific options to display various additional graphical information on the currently computet Voronoi diagram.

(Weighted) Voronoi diagrams

In case of k=1, all n sites are considered having the same color. (Of course each site can have a different drawing color, but that's just an aspect of visualisation that helps to keep apart different sites and their corresponding bisectors. Algorithms don't recognize the sites' color property.) This Applet computes and displays the Voronoi partition of an edited graph. If desired, sites' weights are included in computation. Depending on the type of graph and weighted mode, one of the following algorithms is used (the used algorithm is displayed in the applet's info field):

VDTree - comput. O(m + n log n)
VDGraph - comput. O(e + n log n + m log m)
WVDTree - comput. O(mn log n)
WVDGraph - comput. O(en log n + mn log m)

[applet could not be started]

Explanation of additional display options

VDTree - spanning tree: The spanning tree of all sites may be displayed (the algorithm uses the spanning tree to accelerate computation).
VDGraph - remaining graph: The inner sites of all edges are removed before computation, resulting in the remaining graph.
WVDTree/Graph: The algorithm uses sites' distance functions (refer to the above mentioned paper for further information) for Voronoi computation. These distance functions or their lower envelope can be displayed.

(Weighted) Farthest color Voronoi diagrams

This Applet's algorithms first determine the parameter k as the number of different colors used for the sites, before the farthest color Voronoi diagram is computet. The set of sites is divided into subsets with each subset's sites having the same color. This leads to k different lower envelopes, of which the upper envelope has to be computet. Depending on the type of graph and weighted mode, one of the following algorithms is used (the used algorithm is displayed in the applet's info field):

FCVDTree - comput. O(km + n log n)
FCVDGraph - comput. O(ke log k + n log n + km log m)
WFCVDTree - comput. O(mn(log n + ack²(k) log k))
WFCVDGraph - comput. O(en(log n + ack²(k) log k) + mn log m)

[applet could not be started]

Explanation of additional display options

The algorithms use sites' distance functions (refer to the above mentioned paper for further information) for Voronoi computation. These distance functions, their lower envelopes, their lower envelopes' left and right arms (in non-weighted case) and their lower envelopes' upper envelope can be displayed.

Bibliography

Ferran Hurtado, Rolf Klein, Elmar Langetepe, Vera Sacristán. The weighted farthest color Voronoi diagram on trees and graphs. August 14, 2002.

- Last modified 09-02-2009 10:30