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.
• 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.

If we wanted to be extra careful we would add safeguards against the case where our point has the same x-coord as a segment. 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 find a distance of zero, we simply compare it 'two-back'. We can perform a similar process in 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. The other boundary is handled by intialising our LeftPoint 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:
    • 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 T: \(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 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. 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\). We have overall \(O(m+n)\) space complexity.

Correctedness

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 intervals.
2. Our algorithm finds the closest point to all intervals on the left- and right-hand side.
3. For an interval, the closest point of these two must be the closest point in the whole plane. This is the value we return \(\square\).

Addendum

Just thought I'd let you know; After emailing you about ambiguity in the original question, I proceeded to totally misread the updated version. I spent like four hours working out an algorithm for determining the smallest triangle for each point. It's a much more challenging question.