Xavier Holt edited Assume_we_are_comparing_two__.tex  about 8 years ago

Commit id: 2326b56d7b4dc48f0da2857217a6a86a260ef5d3

deletions | additions      

       

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. We can do so in $O(1)$ by simply comparing the line defined by the angle $\angle mqB\vert_0$ mqb_0$