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

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

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.


\includegraphics[height=40mm]{vtest_draw_de}


next up previous contents
Next: Is it possible to Up: Is it possible to Previous: Is it possible to   Contents
Komei Fukuda 2004-08-26