We devise an efficient algorithm for the computation of the wavefront hull of a bounded set in Z^{n}.

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

Lemma. If m is a nonnegative integer, B_{2m}x = B_{m}V_{m}x (proof trivial).

Corollary. x is in H_{wave}(X) iff V_{m}x ≤ B_{m}X for some nonnegative integer m.

Theorem. Let X be a subset of Z^{n} completely contained in some half-space H = {x in Z^{n} : x_{k }≤ b} and p=(p_{1},...,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_{m}X 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^{n} : x_{k }≥ b}, changing signs as appropriate.

Theorem. Let X be a bounded subset of Z^{n} 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^{n} : σy_{k }≤ b} enclosing XU{x}, dist(x,p) < dist(p,X) where p=(x_{1},...,b,...,x_{n}).

Proof. As x does not belong to H_{wave}(X), V_{m}x is not entirely included in B_{m}X 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_{m}X; 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^{n} : y_{k }≤ b'} which encloses XU{x}. Let H = {y in Z^{n} : y_{k }≤ b} be another arbitrary half-space enclosing XU{x} and p = (x_{1},...,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_{1},b_{1}]x···x[a_{n},b_{n}]**for** *i* = 1 **to** *n····*

**for**every

*p*= (p

_{1},...,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^{2}; 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:

*...*..*

*....*..

***....·

.....**·

## No comments :

## Post a Comment