Xavier Holt edited Smallest_Triangles_A_triangle_s__.md  about 8 years ago

Commit id: f6b8b587a644cdbf3e0c78c2f0003e60433af0be

deletions | additions      

       

## Algorithm  - \(L \leftarrow S \cup P \cup p_{x=\infty}: O(m+n)\)  - Sort \(L\) by ascending x-coordinate: \(O((m+n) \log (m + n) )\)  - T \(\leftarrow\) Empty List  - List,  `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`:  - 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 `t`  from the list: `T`:  \(O(1)\) - `LeftPoint` \(\leftarrow\) `RightPoint`  ## Complexity