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, Zⁿ, with the L₁ distance:

dist((x₁,...,x_n),(y₁,...,y_n)) := ∑|y_i−x_i|.

The picture displays several sets in Z² (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ⁿ.

Theorem. Zⁿ is regular.

Proof. Let X, Y in Zⁿ such that B_rX ≤ B_rY, s ≥ r. Since B_tx = 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_sX \ B_rX 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 η₁,...,η_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−rB_rX. Since by hypothesis B_rX ≤ B_rY, we conclude that x also belongs to B_s−rB_rY ≤ B_sY.

Lemma. If a metric space S is regular, r ≤ s → CB_rCB_rX ≤ CB_sCB_sX for all X in S.

Proof. If x belongs to CB_rCB_rX then B_rx ≤ B_rX, and by the regularity of S B_sx ≤ B_sX, i.e. x belongs to CB_sCB_sX.

Theorem. If X in Zⁿ is bounded, H_wave(X) = CB_rCB_rX for some r ≥ 0.

Proof. Since prisms (cartesian products of n integer intervals) can be easily proved to be convex, H_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≥0CB_rCB_rX = 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_rx ≤ B_rX 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.