Convexity in Zn: hull algorithm

We devise an efficient algorithm for the computation of the wavefront hull of a bounded set in Zⁿ.

Definition. Let x be a point of Zⁿ, r ≥ 0. We define the set V_rx = {x+rδ_i, x−rδ_i: i = 1,...,n}, where δ_i is the element of Zⁿ with i-th coordinate equal to 1, 0 elsewhere. V_rx is the set of extreme points of B_rx.

Lemma. If m is a nonnegative integer, B_2mx = B_mV_mx (proof trivial).

Corollary. x is in H_wave(X) iff V_mx ≤ B_mX for some nonnegative integer m.

Theorem. Let X be a subset of Zⁿ completely contained in some half-space H = {x in Zⁿ : x_k ≤ b} and p=(p₁,...,b,...,p_n) a point on the boundary of H. The points p−iδ_k, 0≤i<dist(p,X), do not belong to H_wave(X).

Proof. For any nonnegative integer m > dist(p,X), p' = p−iδ_k+mδ_k belongs to V_m(p−iδ_k) and does not belong to H. The distance from p' to an arbitrary point x in X is then dist(p',x) = dist(p,x) + m − i ≥ dist(p,X) + m − i > m. So, V_m(p − iδ_k) is not in B_mX and hence the point does not belong to H_wave(X).

Observation. The same result applies for half-spaces of the form H = {x in Zⁿ : x_k ≥ b}, changing signs as appropriate.

Theorem. Let X be a bounded subset of Zⁿ and x a point outside H_wave(X). There is then a coordinate k and a sign σ in {+1,−1} such that for any half-space H = {y in Zⁿ : σy_k ≤ b} enclosing XU{x}, dist(x,p) < dist(p,X) where p=(x₁,...,b,...,x_n).

Proof. As x does not belong to H_wave(X), V_mx is not entirely included in B_mX for any m. Let choose an m greater than max{dist(x,x') : x' in X}: there is a then a point x' = x+mδ_k (or x−mδ_k) outside B_mX; withous loss of generality, let us assume the first variant, which corresponds to σ = +1. By our choice of m, x' lies outside some half-space {y in Zⁿ : y_k ≤ b'} which encloses XU{x}. Let H = {y in Zⁿ : y_k ≤ b} be another arbitrary half-space enclosing XU{x} and p = (x₁,...,b,...,x_n). Using the fact that the k-th coordinates of x' and p are both no less than the k-th coordinate of any point of XU{x}, we have that dist(x,p) = dist(x,x') + p − x_k − m and dist(p,X) = dist(x',X) + p − x_k − m. Since dist(x,x') = m < dist(x',X), it follows that dist(x,p) < dist(p,X).

These theorems allow us to design an efficient algorithm for computing the wavefront hull of a bounded set X:

wavefront hull(X)
{determine the minimum X-enclosing prism P}
P ← [a₁,b₁]x···x[a_n,b_n]
for i = 1 to n
····for every p = (p₁,...,p_n) with p_i = 0 and a_j ≤ p_j ≤ b_j, j ≠ i
········for k = 0 to dist(p+a_iδ_i,X) − 1
············mark(p+(a_i+k)δ_i)
········end for
········for k = 0 to dist(p+b_iδ_i,X) − 1
············mark(p+(b_i−k)δ_i)
········end for
····end for
end for
{return the points of P that have not been marked}

I have written an implementation of the algorithm for Z²; you will need Boost to compile the code. The program accepts from the console input a description of the set X for which to calculate the hull as a number of rows where a character * denotes an element of X and any other character stands for a point outside X, like for instance:

*...*..*
*....*..
***....·
.....**·