** 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