authorea.com/112927

ay5

**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,...}}.

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.

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\).

See: wherever latex decides to put Fig 2. and Fig 3.

N.B: The rule for y/segment nodes is *left* for above, *right* for below.

## Share on Social Media