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?
2 Answers
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
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:
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?).
Related