5
$\begingroup$

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.

$\endgroup$
5
  • 5
    $\begingroup$ 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. $\endgroup$ Commented Aug 31, 2011 at 22:49
  • $\begingroup$ @Suresh Venkat Do you know whether anything is known about the approximation ratio of this heuristic in convex or maybe even general polygons? $\endgroup$
    – 101011
    Commented Feb 6, 2013 at 0:52
  • $\begingroup$ I'm not sure how polygons come into the picture $\endgroup$ Commented Feb 6, 2013 at 6:17
  • $\begingroup$ @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. $\endgroup$
    – 101011
    Commented Feb 6, 2013 at 6:40
  • $\begingroup$ @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). $\endgroup$ Commented Feb 16, 2013 at 1:48

1 Answer 1

13
$\begingroup$

This seems to be equivalent to packing disks of max radius -- a very well studied problem, at least if your box is a square, see, e.g.,Circle packing in a square. For heuristics see, e.g., http://www.pack-any-shape.com/

$\endgroup$
1
  • $\begingroup$ Perfect. Do you know if the pack-any-shape.com code is available anywhere? It's not available directly from the site. $\endgroup$ Commented Sep 1, 2011 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.