Friday, March 7, 2008

Convexity in Zn

We study the generalized concept of convexity defined at a prior entry as applied to the set of n-tuples of integers, Zn, with the L1 distance:

dist((x1,...,xn),(y1,...,yn)) := ∑|yixi|.

The picture displays several sets in Z2 (black cells) along with their wavefront hulls (black and gray cells). The resulting sets do not look at all like traditional convex sets (they do not even have to be connected), however they retain the operational properties of convexity (closed under intersections, etc.)

We investigate now how to calculate wavefront hulls in Zn.

Theorem. Zn is regular.

Proof. Let X, Y in Zn such that BrXBrY, sr. Since Btx = Bfloor(t)x for any radius t, 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) = ∑|xix'i| = ∑σiδis, where δi = xix'i, σi = sign(δi). It is easily seen that we can choose nonnegative integers η1,...,ηn such ηiσiδi and ∑ηi = r. If we define x'' with coordinates x''i = x'i + σiηi, we have 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.

Lemma. If a metric space S is regular, rsCBrCBrXCBsCBsX for all X in S.

Proof. If x belongs to CBrCBrX then BrxBrX, and by the regularity of S BsxBsX, i.e. x belongs to CBsCBsX.

Theorem. If X in Zn is bounded, Hwave(X) = CBrCBrX for some r ≥ 0.

Proof. Since prisms (cartesian products of n integer intervals) can be easily proved to be convex, Hwave(X) is contained in a finite prism enclosing X, and hence Hwave(X) is finite itself, so we can drop all but finitely many terms in the expression Ur≥0CBrCBrX = Hwave(X). By the prior lemma, the remaning elements are contained in that with the largest r.

This theorem allows us to devise a very primitive algorithm to calculate Hwave(X): traverse all the points of the minimun enclosing prism and compute for each point x whether BrxBrX with a large enough value of r (although this would need proof, r = diameter(X) seems to suffice). We will develop more sophisticated techniques at a later entry.

No comments :

Post a Comment