Assignment 2

Supplementary image to Q1.

Fat Points

Proof by contradiction. Assume that the line segment between points \(P,Q\) has maximum pairwise distance, and that \(Q\) does not lie on a vertex. Let the point on the boundary of our hull found by extending the line \(PQ\) be denoted \(Q'\). This boundary segment is defined between two vertices on our convex hull which we refer to as \(A\) and \(B\). See \(\mathbf{Fig. 1}\) for clarification.

Q Lies on the Interior of the Hull

Clearly \(|PQ'|>|PQ|\). In the following section we show that there is always a line-segment longer than \(|PQ'|\). By the transitive property of inequality this segment must also be longer than \(PQ\), a contradiction.

Q Lies on a Hull Edge

In this case, \(Q=Q^{\prime}\). Observe the angles \(\angle PQ^{\prime}A\) and \(\angle PQ^{\prime}B\). WLOG assume \(\angle PQ^{\prime}B\) is the larger of the two and denote it \(\alpha\).

\begin{align} \angle PQ^{\prime}A+\angle PQ^{\prime}B & =\pi\notag \\ \therefore\alpha:=\max\left(PQ^{\prime}A,PQ^{\prime}B\right) & \geq\frac{\pi}{2}\notag \\ \end{align}

As such \(\alpha\) must be the unique largest internal angle in the triangle \(PQ^{\prime}B\). Consequently the side opposite \(\alpha\) \(\left(PB\right)\) is the unique hypotenuse of the triangle. As such \(|PB|>|PQ^{\prime}|\). However \(P\) and \(B\) are both elements of the convex hull so we have found a line segment with length larger than our assumed maximum, a contradiction.

Points of comparison when inserting an interval into the heap.

Points and Planes

We do the exact same thing as the visible-intersection problem in class: radial sweep with a heap.

Algorithm and Runtime

  • Create a set \(\mathcal{P}\) of \(O(n)\) points and \(O(m)\) interval end-points: \(O(m+n)\).
  • Find the point \(m\) with minimum distance to \(q\): \(O(m)\).
  • Sort \(\mathcal{P}\) by angle measured from the line segment \(qm\). If there are multiple non-interval points with the same angle, only include the closest: \(O((m+n)\log (m+n))\).
  • Iterate through these points: \(O(m+n)\)
    • If it's the first end-point of an interval, add the interval to our heap. If it's the second end-point, remove it: \(O (log(m))\)
    • If it's a point, emit if it's closer than the min-heap value: \(O(1)\)

Total running time \(O((m+n)\log (m+n))\).