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.