^{n}, with the L

_{1}distance:

dist((x_{1},...,x_{n}),(y_{1},...,y_{n})) := ∑|y_{i}−x_{i}|.

The picture displays several sets in Z^{2} (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 Z^{n}.

Theorem. Z^{n} is regular.

Proof. Let X, Y in Z^{n} such that B_{r}X ≤ B_{r}Y, s ≥ r. Since B_{t}x = B_{floor(t}_{}_{)}x for any radius t, we can assume without loss of generality that r and s are nonnegative integers. If x belongs to B_{s}X \ B_{r}X there exists some x' in X such that r < dist(x',x) = ∑|x_{i}−x'_{i}| = ∑σ_{i}δ_{i} ≤ s, where δ_{i} = x_{i}−x'_{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) − r ≤ s − r, hence x belongs to B_{s}_{−}_{r}B_{r}X. Since by hypothesis B_{r}X ≤ B_{r}Y, we conclude that x also belongs to B_{s}_{−}_{r}B_{r}Y ≤ B_{s}Y.

Lemma. If a metric space S is regular, r ≤ s → CB_{r}CB_{r}X ≤ CB_{s}CB_{s}X for all X in S.

Proof. If x belongs to CB_{r}CB_{r}X then B_{r}x ≤ B_{r}X, and by the regularity of S B_{s}x ≤ B_{s}X, i.e. x belongs to CB_{s}CB_{s}X.

Theorem. If X in Z^{n} is bounded, H_{wave}(X) = CB_{r}CB_{r}X for some r ≥ 0.

_{wave}(X) is contained in a finite prism enclosing X, and hence H

_{wave}(X) is finite itself, so we can drop all but finitely many terms in the expression U

_{r≥0}CB

_{r}CB

_{r}X = H

_{wave}(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 H_{wave}(X): traverse all the points of the minimun enclosing prism and compute for each point x whether B_{r}x ≤ B_{r}X 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