PROBLEM LINKS
DIFFICULTY
CHALLENGE
EXPLANATION
For small constraints, this problem can be modelled into a Linear programming problem with 2N variables [ 2 variables for co-ordinate of centre of each vertex : xi and yi ] with the Choose(N,2) constraints [ Each constraint for non-intersection of rectangles]. Now, we can use modified Simplex Algorithm to come up with a good solution.
However, there are other approaches as well which can be taken for the problem. We can use divide and conquer to get a reasonable solution to the problem as well. Try breaking the set of vertices into 2 sets, so that the number of edges between the set is as low as possible. Now if you have a solution for each of the 2 sets, try placing the 2 sets adjacent in each of 4 directions and take the best option. This approach gives good results when dealing with squares.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.