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 $i=1,2,3,4,5,6$, we write the inequality system for the facet $F_i$:

$$\begin{array}{ll} & b - A x \ge 0 \text{ and }\\ & b_i - A_i x \le 0 \text{,} \end{array}$$

instead of writing the relaxed inequality (8). For example, for $i=4$, 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 $F_4$, then cdd+ will check which of the given inequalities is redundant or not (essential), by soving the associated LP's (8) for each inequality $j$. As we discussed in 3.5, each inequality for $F_4$, except for the $4$th and the $7$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 $4$th and the $7$th row, and also the lists of numbers after colons. Then we can consider the set $\{1, 2, 6\}$ of essential constraints as the set of indices of Voronoi cells adjacent to the $4$th cell. Of course, this adjacency coincides with the adjacency of input points in the Delaunay triangulation. See the figure below.