The Stack Overflow podcast is back! Listen to an interview with our new CEO.
2 of 2 added 3 characters in body

My gut feeling tells me that this is an NP-complete problem. You can try to find a good solution but not the best one.

So yes, a start would be to pick three points in the middle, start there and create a triangle. Find the closest points to each of these three points and try to create a new rectangle. It should give a decent solution in most cases.

To improve on this, you could run it multiple times with a number of different starting triangles. Or add some randomness to the taking of the closest points. Run it a few times and keep the best solution you've found.