Xavier Holt edited Smallest_Triangles_A_triangle_s__.md  about 8 years ago

Commit id: 34756a843febcbc767a840b17a4637b71d57abf9

deletions | additions      

       

- Sort \(L\) by ascending x-coordinate: \(O((m+n) \log (m + n) )\)  - T \(\leftarrow\) Empty List  - LeftPoint `LeftPoint`  \(\leftarrow -\infty\) - For each element in \(L\): O(m+n)   - If it's an interval, store it in \(T\)  - If it's a point denote it RightPoint: `RightPoint`:  - For each interval \(t\) in T: RTP amortised \(O(1)\).  - Compare `dist(t,LeftPoint)` and `dist(t, rightPoint)`. Emit a tuple of \(t\) and the argmin of these two distances: \(O(1)\).  - Remove t from the list: \(O(1)\)  - `LeftPoint` \(\leftarrow\) `RightPoint`  ## Complexity  Our runtime depends on the inner loop being amortised \(O(1)\). This is clear as an interval is included in a list exactly once before being remove. As such, the total number of elements in the list is \(O(n)\) and so per outer-loop iteration we have amortised \(O(1))\).