Xavier Holt edited Points_and_Planes_We_basically__.md  about 8 years ago

Commit id: 400f44e232766b651e5eb85ced832cf69c4d8add

deletions | additions      

       

### Algorithm and Runtime  *  Create a set \(\mathcal{P}\) of \(O(n)\) points and \(O(m)\) interval end-points (\(O(m+n)\)). end-points: \(O(m+n)\).  *  Find the point \(m\) with minimum distance to \(q\) (\(O(m+n)\)). \(q\): \(O(m+n)\).  *  Sort \(\mathcal{P}\) by angle measured from the line segment \(qm\) (\(O((m+n)\log (m+n))\)). \(qm\): \(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+n))\)  * If it's a point, emit if it's closer than the min-heap value: \(O(1)\)  Iterate through these points (\(O(m+n)\)). Total running time \(O((m+n)\log (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+n))\))  * If it's a point, emit if it's closer than the min-heap value \(O(1)\). ### Heap  Total running time (\(O((m+n)\log (m+n))\)).  ### Correctedness