5

I am given a set of N points in 2D plane represented as (x,y) coordinate pairs. What is a fast algorithm to choose three points so that the triangle formed by these points has maximum perimeter?

David
  • 51
  • 2
  • 1
    Brute force is the only way. So time complexity is `O(n^3)`. – nice_dev Sep 03 '18 at 20:28
  • 2
    Actually the number of triangles to check in a brute force algorithm would be (n choose 3), which is ~ (n^3)/6, so complexity would indeed be O(n^3). You can ignore points not part of the convex hull, and points along a straight line, but in the worst case you still have n points. – m69's been on strike for years Sep 03 '18 at 21:24
  • Possible duplicate of [How to find largest triangle in convex hull aside from brute force search](https://stackoverflow.com/questions/1621364/how-to-find-largest-triangle-in-convex-hull-aside-from-brute-force-search) – Richardissimo Sep 03 '18 at 21:43
  • @Richardissimo Is the solution for largest area guaranteed to work for largest perimeter too? (Improving abc into abd would mean d is beyond a line through c parallel to ab for area, and d is outside an ellipse through c with focal points a and b for perimeter.) – m69's been on strike for years Sep 03 '18 at 21:50
  • Ah apologies, my mistake. The largest perimeter does not correlate to the largest area. (Withdrawn suggestion of duplicate.) – Richardissimo Sep 03 '18 at 21:54

2 Answers2

0

This is preemptive in nature

  • Pick a point farthest from the flock, lets call it point A.
  • draw an imaginary straight line that cuts through A to rest of the flock.
  • pick another opposite point, that its deviation(from the imaginary straight line) is highest to right.
  • pick another opposite point, that is deviation(from the imaginary straight line) is highest to the left.

Check if a triangle can be made?. if no check another highest point in another axis

Declan Nnadozie
  • 1,805
  • 1
  • 10
  • 20
0

Here's a rough idea (I'm not too versed in computational geometry). A triangle with a fixed perimeter and base can generate an ellipse. For example, here B and C are fixed and any point, A, on the ellipse will keep the triangle perimeter the same:

enter image description here

For each segment connecting two points, pick a random third point in our set. Generate the relevant ellipse, then pick another random point from our set that's outside that ellipse. Each ellipse will exclude points that generate triangles of the same or smaller perimeter until we run out of points, having found the largest. Of course, we would need some efficient methods to find relevant points (perhaps using space partitioning?).

גלעד ברקן
  • 23,602
  • 3
  • 25
  • 61
  • I suspect that for adjacent points a,b,c,d,e on the convex hull, if |abd| > |acd| and |bde| > |cde| then |bdx| > |cdx| for all points x on the convex hull, and thus cd cannot be a side of the largest-perimeter triangle. But I haven't been able to come up with a proof. – m69's been on strike for years Sep 04 '18 at 18:05