Convexity in (Zn,L∞)

After having studied our generalized convexity concept for (Zⁿ,L₁), we investigate now the L_∞ metric:

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

As we will see, the analysis is entirely analogous as that of (Zⁿ,L₁).

Theorem. (Zⁿ,L_∞) is regular.

Proof. Let X, Y in Zⁿ such that B_rX ≤ B_rY, s ≥ r. Similarly as how we saw in the L₁ case, 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_k−x'_k| ≤ s, for some k in {1,...,n}. Let x'' be the point defined by x''_k = x'_k + sign(x_k−x'_k) r, x''_i = x'_i for i ≠ k. Then, 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.

The role played in (Zⁿ,L₁) by the set of extreme points of B_rx, V_rx = {x+rδ_i, x−rδ_i: i = 1,...,n}, and by separating half-spaces of the form H = {y in Zⁿ : σy_k ≤ b}, with σ in {+1,−1}, is played in (Zⁿ,L_∞) by correlates of these structures. We state the theorems without proof as they follow the same lines as the equivalent propositions for (Zⁿ,L₁).

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

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

Lemma. x is in H_wave(X) iff V_mx ≤ B_mX for some nonnegative integer m.

Definition. We say that a point p lies beside a half-space H = {x in Zⁿ : xv ≤ b}, where v is a ±1-vector, if pv ≥ b 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 Zⁿ : xv ≤ b} include, but are not limited to, those with pv = b. The figure shows the situation for Z². 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 Zⁿ completely contained in some half-space H = {x in Zⁿ : xv ≤ b}, where v is a ±1-vector, and p a point lying beside H. The points p−iv, 0≤i<dist(p,X), do not belong to H_wave(X).

Theorem. Let X be a bounded subset of Zⁿ and x a point outside H_wave(X). There is then a ±1-vector v such that for any half-space H = {y in Zⁿ : 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 (Zⁿ,L₁) we traversed the boundary of an enclosing prism P, here we must work with an enclosing rhombic prism with each of its 2ⁿ faces lying at a hyperplane of the form π = {x in Zⁿ : xv = b}, with v a ±1-vector.

wavefront hull(X)
{determine the minimum X-enclosing rhombic prism P}
P ← ∏H_i, H_i = {x in Zⁿ : xv_i ≤ b_i}, v_i is a ±1-vector, i = 1,...,2ⁿ
for i = 1 to 2ⁿ
····for every p in P with p beside H_i and p in H_j, j ≠ i
········for k = 0 to dist(p,X) − 1
············mark(p−kv_i)
········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 Z² and compare the results with the L₁ case.