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