Assume we are comparing two intervals \(A\) and \(B\). Let \(A\) be the interval stored in-heap and \(B\) the interval we’ve just encountered. Our points of interest are the first end-point of \(B\) which we denote \(b_{0}\) and the point on \(A\) which intersects the radial scan line at this point, which we refer to as \(a_{\alpha}\) (Fig. 2). We can find this in \(O(1)\) by comparing the equations of the radial-line and the interval. Our heap property is defined in terms of the distance of those points measured from \(q\). When we are making a point (not interval) comparison we repeat the process above with our point of interest taking the place of \(b_{0}\).
The ordering of \(A\) and \(B\) is invariant of scanline position.
N.B: For ease of notation, we assume we have re-centered our axes at query point \(q\), that is \(\|x\|\equiv\|x-q\|\).
This follows immediately from the continuity of our intervals and the given non-intersection.
To see why assume the opposite. Say we had two intervals \(A\) and \(B\) as above with \(\|b_{0}\|\leq\|a_{\alpha}\|\). Assume the ordering changed by scan-angle \(\phi\), that is \(\|a_{\phi}\|\leq\|b_{\phi}\|\). If we define the function \(f(\theta):=\|a_{\theta}\|-\|b_{\theta}\|\), then by rewriting the conditions above:
Our function is continuous, so by the intermediate value theorem there has to be some value in the range of the function where \(f(x)=0\). This implies that at some angle of the scanline \(x\), \(\|a_{x}\|=\|b_{x}\|\). In polar coordinates we’ve uniquely defined a point in the plane that both intervals occupy. This contradicts the non-intersection of our intervals. ∎
This lemma indicates that it is sufficient to compare intervals at one angle of the scanline.