this is for holding javascript data
Xavier Holt edited Smallest_Triangles_scan_L_to__.md
about 8 years ago
Commit id: d65889e0a1db924ba7e113a6aadf7f0416237c31
deletions | additions
diff --git a/Smallest_Triangles_scan_L_to__.md b/Smallest_Triangles_scan_L_to__.md
index 3f09f82..ae67005 100644
--- a/Smallest_Triangles_scan_L_to__.md
+++ b/Smallest_Triangles_scan_L_to__.md
...
# Smallest Triangles
A triangle's area is determined by perpendicular distance to a point. As such, we can throw away the y-coordinates for both the segments and points.
- scan L to R
- we can reduce to a 1D problem
- x- coords and length of thing
if smallest and closest then match
for a and b *Handle the case where coordinates are equal*
if ## Algorithm
elementary intervals thing - \(L \leftarrow S \cup P: O(m+n)\)
- Sort \(L\) by ascending x-coordinate: \(O((m+n) \log (m + n) )\)
- T \(\leftarrow\) Empty 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: Amortised \(O(1)\) as we handle each interval exactly once across all loop iterations.
- 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)\)
## Runtime
Running time is \(O((m+n) \log (m + n) )\) for the preprocessing and \(O(m+n)\) in the loop for a total of \(O((m+n) \log (m + n) )\).