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.