Tuesday, April 8, 2008

Convexity in (Zn,L)

After having studied our generalized convexity concept for (Zn,L1), we investigate now the L metric:

dist((x1,...,xn),(y1,...,yn)) := max{|yixi|}.

As we will see, the analysis is entirely analogous as that of (Zn,L1).

Theorem. (Zn,L) is regular.

Proof. Let X, Y in Zn such that BrXBrY, sr. Similarly as how we saw in the L1 case, we can assume without loss of generality that r and s are nonnegative integers. If x belongs to BsX \ BrX there exists some x' in X such that r < dist(x',x) = |xkx'k| ≤ s, for some k in {1,...,n}. Let x'' be the point defined by x''k = x'k + sign(xkx'k) r, x''i = x'i for ik. Then, dist(x',x'') = r, dist(x'',x) = dist(x',x) − rsr, hence x belongs to BsrBrX. Since by hypothesis BrXBrY, we conclude that x also belongs to BsrBrYBsY.

The role played in (Zn,L1) by the set of extreme points of Brx, Vrx = {x+i, xi: i = 1,...,n}, and by separating half-spaces of the form H = {y in Zn : σyk b}, with σ in {+1,−1}, is played in (Zn,L) by correlates of these structures. We state the theorems without proof as they follow the same lines as the equivalent propositions for (Zn,L1).

Definition. A point of Zn is said to be a ±1-vector if all its coordinates are either +1 or −1.

Definition. Let x be a point of Zn, r ≥ 0. Let Vrx = {x+rv: v is a ±1-vector}. Vrx is the set of extreme points of Brx.

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

Definition. We say that a point p lies beside a half-space H = {x in Zn : xv b}, where v is a ±1-vector, if pvb and (p v)v < b and , i.e. pv is in [b,b+n).

Note that the points lying beside a half-space H = {x in Zn : xv b} include, but are not limited to, those with pv = b. The figure shows the situation for Z2. The key property of this definition is that any point x in H will intersect one and only one point lying beside H when drawing a ray starting from x along the the normal direction to H, v.

Theorem. Let X be a subset of Zn completely contained in some half-space H = {x in Zn : xv b}, where v is a ±1-vector, and p a point lying beside H. The points piv, 0≤i<dist(p,X), do not belong to Hwave(X).

Theorem. Let X be a bounded subset of Zn and x a point outside Hwave(X). There is then a ±1-vector v such that for any half-space H = {y in Zn : yv b} enclosing XU{x}, dist(x,p) < dist(p,X) where p lies beside H and is of the form x + kv for some k ≥ 0.

If in the waterfront hull algorithm for (Zn,L1) we traversed the boundary of an enclosing prism P, here we must work with an enclosing rhombic prism with each of its 2n faces lying at a hyperplane of the form π = {x in Zn : xv = b}, with v a ±1-vector.

wavefront hull(X)
{determine the minimum X-enclosing rhombic prism P}
PHi, Hi = {x in Zn : xvi bi}, vi is a ±1-vector, i = 1,...,2n
for i = 1 to 2n
····
for every p in P with p beside Hi and p in Hj, ji
········for k = 0 to dist(p,X) − 1
············mark(pkvi)
········end for
····end for
end for
{return the points of P that have not been marked}

In a later entry we will provide an implementation of the algorithm for Z2 and compare the results with the L1 case.

No comments :

Post a Comment