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