this is for holding javascript data
Xavier Holt edited Smallest_Triangles_A_triangle_s__.md
about 8 years ago
Commit id: 67eddd3d37554aa221fdc660d3f22df65e6bb3ae
deletions | additions
diff --git a/Smallest_Triangles_A_triangle_s__.md b/Smallest_Triangles_A_triangle_s__.md
index 5c5312e..c9f0e2a 100644
--- a/Smallest_Triangles_A_triangle_s__.md
+++ b/Smallest_Triangles_A_triangle_s__.md
...
- When considering a single interval the width is fixed. As such, the minimum area triangle is found by simply finding the closest point in terms of perpendicular distance
- We scan from L to R. For each segment, we determine the points closest on the left and right. We compare the distance from our segment to each, and return the point of minimum distance.
- We should also consider when If we wanted to be extra careful we would add safeguards against the case where our point
lies directly below or above has the same x-coord as a segment.
In We would want to do this as we can't make a triangle with three colinear points.
We can identify this case
by noting when our `dist(t,.)` function is zero. We can resolve it by keeping track of two previous points at any time (that we ensure have different x-values). When we
would find a
`dist` distance of zero,
and would we simply
add compare it 'two-back'. We can perform a similar process in the
interval back into the... other direction, storing a point until we have two points with `dist!=0` on either side. We have omitted this process from our algorithm for brevity.
## Algorithm
- \(L \leftarrow S \cup P \cup p_{x=\infty}: O(m+n)\)
- _N.B: We add a point with x-coordinate \(\infty\) to our point set to handle the boundary case of segments occurring after our last
point._
- Sort \(L\) point. The other boundary is handled by
ascending x-coordinate: \(O((m+n) \log (m + n) )\)
- T \(\leftarrow\) Empty List, intialising our `LeftPoint`
\(\leftarrow -\infty\) as below_
- T \(\leftarrow\) Empty List, `LeftPoint` \(\leftarrow -\infty\)
- Sort \(L\) by ascending x-coordinate: \(O((m+n) \log (m + n) )\)
- 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`:
...
## 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 removed. The total number of elements in the list is \(O(n)\) and so per outer-loop iteration we have amortised \(O(1))\).
**Time**: Running time is \(O((m+n) \log (m + n) )\) for the preprocessing and \(O(m+n)\) in the
loop for a total loop. Total of \(O((m+n) \log (m + n) )\).
**Space**: We require \(O(m+n)\) space for the sorted elements and an additional \(O(m+n)\) in total for the list \(T\).
As such we We have overall \(O(m+n)\) space complexity.
## Correctedness
For all segments 1. Triangle areas are a product of perpendicular distance and length. When length is fixed, we minimise area by finding the closest point to our
program intervals.
2. Our algorithm finds the
two points immediately on their left or right. The minimum area triangle has closest point to
be formed by one of these, as any other all intervals on the left- and right-hand side.
3. For an interval, the closest point
will have larger perpendicular distance than at least one of
them. As we report these two must be the
minimum of closest point in the
triangles made by whole plane. This is the
left and right points, value we
report the global smallest triangle for each segment. return \(\square\).