## Monday, March 24, 2008

### Convexity in Zn: hull algorithm

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

Definition. Let x be a point of Zn, r ≥ 0. We define the set Vrx = {x+i, xi: i = 1,...,n}, where δi is the element of Zn with i-th coordinate equal to 1, 0 elsewhere. Vrx is the set of extreme points of Brx.

Lemma. If m is a nonnegative integer, B2mx = BmVmx (proof trivial).

Corollary. x is in Hwave(X) iff VmxBmX for some nonnegative integer m.

Theorem. Let X be a subset of Zn completely contained in some half-space H = {x in Zn : xk b} and p=(p1,...,b,...,pn) a point on the boundary of H. The points pk, 0≤i<dist(p,X), do not belong to Hwave(X).

Proof. For any nonnegative integer m > dist(p,X), p' = pk+k belongs to Vm(pk) 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) + midist(p,X) + mi > m. So, Vm(pk) is not in BmX and hence the point does not belong to Hwave(X).

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

Theorem. Let X be a bounded subset of Zn and x a point outside Hwave(X). There is then a coordinate k and a sign σ in {+1,−1} such that for any half-space H = {y in Zn : σyk b} enclosing XU{x}, dist(x,p) < dist(p,X) where p=(x1,...,b,...,xn).

Proof. As x does not belong to Hwave(X), Vmx is not entirely included in BmX for any m. Let choose an m greater than max{dist(x,x') : x' in X}: there is a then a point x' = x+k (or xk) outside BmX; 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 Zn : yk b'} which encloses XU{x}. Let H = {y in Zn : yk b} be another arbitrary half-space enclosing XU{x} and p = (x1,...,b,...,xn). 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 xk m and dist(p,X) = dist(x',X) + p xk 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 ← [a1,b1]x···x[an,bn]
for i = 1 to n
····
for every p = (p1,...,pn) with pi = 0 and ajpjbj, ji
········for k = 0 to dist(p+aiδi,X) − 1
············mark(p+(ai+k)δi)
········end for
········for k = 0 to dist(p+biδi,X) − 1
············mark(p+(bik)δ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 Z2; 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:

`*...*..**....*..***....·.....**·`