Errata for Technical Report “Quaderno 286”

Roberto Bagnara^{1}, Elisa Ricci^{1}, Enea Zaffanella^{1}, and Patricia M. Hill^{2}

1 Department of Mathematics, University of Parma, Italy 2 School of Computing, University of Leeds, UK

The following conjecture (mis-named claim) was made in [1, pp. 13-14].

Claim. Let R ⇛_{ϵ} P ≠ ∅, where (C, G) ≡ R is a minimal DD pair.

1. If C is in smf and either C_{ϵ} = ∅ or con(C \ C_{ϵ}) ⇛̸_{ϵ} P, then G is in smf.

2. If G is in smf and all the point encodings in G_{P} have the same value for the ϵ coordinate, then C is in smf.

These statements do not affect any other part of the cited paper and are not exploited in the implementation of the Parma Polyhedra Library described there. Nonetheless, both statements are false. To see this, we provide the following two counter-examples.

Counterexample to 1

Consider the polyhedron P ∈ ℙ_{2} where

P = { (x, y)^{T} ∈ ℝ^{2} | x > 0, y > 0, x < 3, y < 2 }.

Then R = con(C) ∈ ℂℙ_{3} is an ϵ-representation for P where

C = {x − ϵ ≥ 0, y − ϵ ≥ 0, −x − ϵ ≥ −3, −y − ϵ ≥ −2, ϵ ≥ 0}.

Note that the constraint ϵ ≤ 1 is a consequence of the second and fourth of these constraints. Thus we have C_{≥} = C_{ϵ} = ∅. Then R (which may be visualized as a ridge or roof shape) is generated by G = (R, P) where R = ∅ and the point encodings G_{P} and closure point encodings G_{C} are as follows:

G_{C} = {(0, 0, 0)^{T}, (0, 2, 0)^{T}, (3, 0, 0)^{T}, (3, 2, 0)^{T}},
G_{P} = {(1, 1, 1)^{T}, (2, 1, 1)^{T}}.

Observe that C contains no ϵ-redundant constraints and hence is in smf, However, the point p = (1, 1, 1)^{T} is in G_{U} so that (letting p′ = (2, 1, 1)^{T} in Definition 7) p is ϵ-redundant in G. Therefore G is not in smf.

Counterexample to 2

Consider the polyhedron P = {0} ∈ ℂℙ_{1}. Then R = gen(G) ∈ ℂℙ_{2} is an ϵrepresentation for P where the generator system G = (R, P) is such that R = ∅ and P is the union of the closure point encodings G_{C} = {(0, 0)^{T}} and point encodings G_{P} = {(0, 1)^{T}}. As G_{P} is a singleton, G is in smf for any constraint system defining R. Moreover, the condition that all point encodings have the same value for ϵ is satisfied trivially. Consider the constraint system

C = {x ≤ 0, x ≥ 0, ϵ ≥ 0, x − ϵ ≥ −1},

which is in minimal form. As the only point (0, 0)^{T} in G_{C} does not saturate c = (x − ϵ ≥ −1), c is ϵ-redundant (using the first condition in Definition 7). Therefore C is not in smf.

References

1. R. Bagnara, E. Ricci, E. Zaffanella, and P. M. Hill. Possibly not closed convex polyhedra and the Parma Polyhedra Library. Quaderno 286, Dipartimento di Matematica, Università di Parma, Italy, 2002. Available at http://www.cs.unipr.it/

   Publications/.