Next: Is it possible to Up: Is it possible to Previous: Is it possible to   Contents

Sample session with cdd+

With cdd+, a setup for computing the adjacency of Voronoi cells is quite simple. Consider the same example 3.4.1. For each input point , we write the inequality system for the facet :

instead of writing the relaxed inequality (8). For example, for , we have

H-representation
begin
7   4   real
0  0  0  1
5 -4 -2  1
5 -2 -4  1
16 -8  0  1
16  0 -8  1
32 -8 -8  1
-16  8  0 -1  % negative of 4th inequality
end
facet_listing

The last inequality is the negative of the forth inequality to force the forth inequality to be equality.

The code cdd+ has an option called facet_listing''. If we apply this option to the facet , then cdd+ will check which of the given inequalities is redundant or not (essential), by soving the associated LP's (8) for each inequality . As we discussed in 3.5, each inequality for , except for the th and the th one,

The program cdd+ will output a file:

*Facet listing is chosen.
* e means essential and r means redundant.
begin
1 e: 2 7 1
2 e: 2 7 1
3 r: 2 7 6
4 e: 4 2 6
5 r: 7 2 6
6 e: 7 2 6
7 e: 7 2 6
end

We simply ignore the th and the th row, and also the lists of numbers after colons. Then we can consider the set of essential constraints as the set of indices of Voronoi cells adjacent to the th cell. Of course, this adjacency coincides with the adjacency of input points in the Delaunay triangulation. See the figure below.

Next: Is it possible to Up: Is it possible to Previous: Is it possible to   Contents
Komei Fukuda 2004-08-26