# Place n points in a box as far away from each other as possible

Can you suggest an optimal or heuristic algorithm for placing points on a 2D plane (within a constrained space) such that minimum distance between any two points is maximized.

In other words, I'm looking to put points down in a box as far away from each other as possible.

• A standard heuristic is the Gonzalez trick, where you place the first, place the second as far away as possible, the third as far away as possible from the first two, and so on. Commented Aug 31, 2011 at 22:49
• @Suresh Venkat Do you know whether anything is known about the approximation ratio of this heuristic in convex or maybe even general polygons? Commented Feb 6, 2013 at 0:52
• I'm not sure how polygons come into the picture Commented Feb 6, 2013 at 6:17
• @Suresh Venkat Well in the original problem we are given a box and I just thought that a polygon would be a natural generalization of it. Commented Feb 6, 2013 at 6:40
• @chen The approximation factor is 2 for the Gonzalez approximation algorithm, but the problem it requires a "grid" to be placed on the map. The finer the grid, the longer the running time (though polynomial in the number of grid points). Commented Feb 16, 2013 at 1:48