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.

  • 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$ – Suresh Venkat Aug 31 '11 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 Feb 6 '13 at 0:52
  • $\begingroup$ I'm not sure how polygons come into the picture $\endgroup$ – Suresh Venkat Feb 6 '13 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 Feb 6 '13 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$ – Alan Turing Feb 16 '13 at 1:48

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/

| cite | improve this answer | |
  • $\begingroup$ Perfect. Do you know if the pack-any-shape.com code is available anywhere? It's not available directly from the site. $\endgroup$ – Alan Turing Sep 1 '11 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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