Main Data History
Show Index Toggle 0 comments
  •  Quick Edit
  • 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,...}}.


    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.


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