^{n},L

_{1}), we investigate now the L

_{∞}metric:

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

As we will see, the analysis is entirely analogous as that of (Z^{n},L_{1}).

Theorem. (Z^{n},L_{∞})^{} is regular.

Proof. Let X, Y in Z^{n} such that B_{r}X ≤ B_{r}Y, s ≥ r. Similarly as how we saw in the L_{1} case, 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_{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}_{−}_{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.

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

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

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

Lemma. x is in H_{wave}(X) iff V_{m}x ≤ B_{m}X for some nonnegative integer m.

Definition. We say that a point p lies beside a half-space H = {x in Z^{n} : 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^{n} : xv_{ }≤ b} include, but are not limited to, those with pv = b. The figure shows the situation for Z^{2}. 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^{n} completely contained in some half-space H = {x in Z^{n} : 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^{n} 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^{n} : 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^{n},L_{1}) we traversed the boundary of an enclosing prism P, here we must work with an enclosing rhombic prism with each of its 2^{n} faces lying at a hyperplane of the form π = {x in Z^{n} : 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^{n} : xv_{i }≤ b_{i}}, v_{i }is a ±1-vector, i = 1,...,2^{n}**for** *i* = 1 **to** 2^{}^{n}

····**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^{2} and compare the results with the L_{1} case.^{}

## No comments :

## Post a Comment