<p>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.,<a href="http://en.wikipedia.org/wiki/Circle_packing_in_a_square" rel="nofollow">Circle packing in a square</a>. For heuristics see, e.g., <a href="http://www.pack-any-shape.com/" rel="nofollow">http://www.pack-any-shape.com/</a></p>

CC BY-SA 3.0
2011-09-01T02:48:41.857Z
Perfect. Do you know if the [pack-any-shape.com](http://www.pack-any-shape.com/) code is available anywhere? It's not available directly from the site.
Alan Turing
CC BY-SA 3.0
2011-08-31T23:50:16.190Z
2011-09-01T16:46:23.287Z
2011-09-01T16:46:23.287Z
val
<p>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.</p>

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

CC BY-SA 3.0
2011-08-31T22:49:36.527Z
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.
Suresh Venkat
CC BY-SA 3.0
2013-02-06T00:52:41.720Z
@Suresh Venkat Do you know whether anything is known about the approximation ratio of this heuristic in convex or maybe even general polygons?
101011
CC BY-SA 3.0
2013-02-06T06:17:55.883Z
I'm not sure how polygons come into the picture
Suresh Venkat
CC BY-SA 3.0
2013-02-06T06:40:50.917Z
@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.
101011
CC BY-SA 3.0
2013-02-16T01:48:28.467Z
@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).
Alan Turing
<graph-theory><cg.comp-geom><optimization><topology><topological-graph-theory>
Place n points in a box as far away from each other as possible
Alan Turing
# Place n points in a box as far away from each other as possible

(Asked by: username_0 on 2011-08-31)

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.

**Tags:** graph-theory, cg.comp-geom, optimization, topology, topological-graph-theory
> **Comments:**
> **username_1**: 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.  
> **username_2**: @Suresh Venkat Do you know whether anything is known about the approximation ratio of this heuristic in convex or maybe even general polygons?  
> **username_1**: I'm not sure how polygons come into the picture  
> **username_2**: @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.  
> **username_0**: @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).  

---

## 1 answers

### Answer by username_3 on 2011-08-31. Score: 13

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](http://en.wikipedia.org/wiki/Circle_packing_in_a_square). For heuristics see, e.g., <http://www.pack-any-shape.com/>

> **Comments:**
> **username_0**: Perfect. Do you know if the [pack-any-shape.com](http://www.pack-any-shape.com/) code is available anywhere? It's not available directly from the site.  

---

