# WSPD

a) One by definition of the WSPD.

b) Depends on decomposition/points chosen. In general it can be $$1$$ to $$n-1$$.

For lower bound, we can make a WSPD of a point that has all pair of points as singleton sets. In our example this WSPD would look like {{a}{b}} {{a}{c}} {{b}{c}}. This is always a valid WSPD for any pointset/s and we have that all pairs appear in the union of some subset-pair once.

In terms of a lower bound, consider a WSPD of the form {{a}, {b}}, {{a,b}, {c}} {{a,b}, {d}}, etc. We assume here that this is valid, i.e. all points lie further than sr from the {a,b} circle (which is clearly s * dist(a,b)). In this case a,b appear in n-1 of the unions.

c) Given $$s\geq 2$$ $$|A|=|B|=1$$. Proof is simple and given in lectures. Basically, if p and q are the closest points and $$s\geq 2$$ then any point within either of their WSP-sets would have to be closer, a contradiction.

d) $$|A|=1$$ from above, $$|B| \in[1,n-1]_\mathbb{N}$$. Lower bound when p,q are the closest two points, upper bound when we have {{a}{b,c,...}}.

# H-Distance

## Algorithm and Runtime

Below we indicate how to calculate $$H(B,A)$$.

• V $$\leftarrow$$ a Voronoi diagram of A: $$O(n\log n)$$
• D $$\leftarrow$$ trapezoidal point-decomp on V. Voronoi diagrams have $$O(n)$$ edges, .:. this step has expected $$O(n\log n)$$ run-time.
• $$H_{B,A}$$ $$\leftarrow$$ 0
• $$\forall$$ b $$\in$$ B: $$O(n)$$
• a $$\leftarrow$$ The point corresponding to the Voronoi cell in which b resides, found using D:$$O(\log n)$$
• d $$\leftarrow$$ dist(a,b)
• $$H_{B,A}$$ $$\leftarrow$$ $$\max\left\{H_{B,A},d\right\}$$ : $$O(1)$$.

Our overall run-time is expected $$O(n\log n)$$. We can repeat the exact same steps exchanging A for B to calculate H(A,B) in $$O(n\log n)$$ expected. We then simply return the larger of the two.

## Correctedness

For all b, we find the cell in the Voronoi diagram in which it resides and the point a corresponding to this point. From the definition of the Voronoi diagram, the distance between these points is $$d(b,A)$$. We do so for all $$b$$ and return the maximum, i.e. $$\max_{b\in B} d(b,A) =: H(B,A))$$.

We repeat this for $$H(A,B)$$ and return the maximum, i.e. $$\max \left\{H(A,B), H(B,A) \right\} =: D(A,B) \ \square$$.

Art