Close-packing points in the plane?

Question

Suppose that I have a complete, undirected graph G with a distance associated with each edge. The meaning of edge (u, v) having length l is "points u and v can't be any closer to each other than l." My goal is to lay the nodes of this graph out in a plane so that none of these distance constraints are violated and such that the convex hull of the points has the least total area. As an example, suppose that I have a bunch of electrical components I want to put onto a chip, each of which generates some amount of electrical interference. If I put the components too close together, they'll start interfering with one another, rendering the whole system useless. Given the minimum distances each point should be from each other point, what's the most space-efficient way of putting the components on a chip?

I have no idea how to even start thinking about this. I also don't know how the problem might generalize to the higher-dimensional case (packing points into a hyperplane). Does anyone know of a good way of tackling this problem?

Homophile

You want to look up Graph Drawing. Force-directed techniques could give you a good result for this case. – Piecedyed

@novalis- I'm aware of these techniques, but to the best of my knowledge there are no proofs that these give optimal solutions (or even anything close to an optimal solution). I'm looking for an algorithm that would be within some predictable factor of optimal. – Homophile

Rather than area of the convex hull (per Chris Hopman's answer), you probably want to minimize something like the product of the aspect ratio and the radius from the centroid to the furthest point. I'm assuming for this to be meaningful that your graph is completely dense - you don't have components that can 'stack' in the same position? – Oscilloscope

There must be some contraints on the length of the edges for the problem to have a solution. The edges must satisfy a bunch of inequalities. Maybe only checking for triangle inequalities will do, but perhaps not. – Recede

@Alexnandre C.- Do there need to be these inequalities? For example, breaking the triangle inequality seems like it should be fine, since any solution would still have to obey the longest edge of the triangle. – Homophile

Answer 1

I have an optimal solution, but you aren't going to like it :).

Let's label our nodes x₀, x₁, ..., x_n. Let B = max_{i,j < n}(dist(x_i, x_j)), where dist(x_i, x_j) is the minimum distance between x_i and x_j. For each i, place node x_i at position (0, i*B). Now each node is at least B away from all the others, and the convex hull has area 0.

The real point here is that minimizing the area of the convex hull alone will give you a nonsensical solution. A possibly better measure would be the diameter of the convex hull.

Epsom

That's an extremely good point. If you do set up the problem to work with the diameter, do you have any thoughts? You seem to be a major algorithms wizard, and I'd love to hear your thoughts on the problem. – Homophile

Answer 2

I guess it'll be hard to find the optimal algorithm. I wouldn't be surprised if it turned out to be an NP-hard problem. However, if you're interested in a practical algorithm that yields decent solutions, I recommend to take a look at force-based graph drawing algorithms.

Here's the general idea (some higher math. will appear). It generalizes to any number of dimensions.

Construct a function f which assigns a value to each node layout – a value that you want to minimize. In your case, the function could calculate the area of the convex hull for a given layout + a big penalty for each constraint that wasn't met. Or it could be a simpler function g which reasonably approximates the former one: in short, we want g to get smaller whenever f gets smaller, and vice versa. It is good to choose a relatively simple function, because you will need to calculate its partial derivatives (with respect to coordinates of nodes).

Now let's say you've got 100 nodes and you want to lay them out in 3D. That means you have 300 unknown numbers (100 nodes times 3 coordinates for each node). Function f is a function from R³⁰⁰ to R, and ideally we want to find it's global minimum. More realistically, a sufficiently deep local minimum will suffice.

There are well known numerical algorithms for finding such a minimum, for example: Conjugate gradient, BFGS. Good thing is, you don't really have to understand them in details, these algorithms are implemented in many languages. All you have to do is to provide a method of calculating f(x) and f'(x) for any x requested by the algorithm, and an initial layout x₀.

Halsey

I actually thought about doing this for a while, but the fact that I have no guarantee that the resulting graph is anywhere near optimal always turned me off to it. – Homophile

For practical purposes you can run the algorithm as many times as you can afford with different (random) initial layouts, and the best result should be satisfactory. Of course, there is still no guarantee that you arrive anywhere near optimum. It's a very interesting problem from a theoretical standpoint! – Halsey

Answer 3

It's 2D bin packing problem (which is NP hard) with extra constraints. I've heard simulated annealing performs pretty well for circuit/chip design.

I am actually looking for real-world test-data of a big bin packing problem for Drools Planner.

Ironclad

Simulated annealing is indeed great for such problems. Finding where to place points for meshing a domain (with constraints: triangles must be "fat" and their diameter must be distributed as some density on the domain) looks quite similar, and can be solved with SA. – Recede

I'm not sure I follow... You're saying that this is NP-hard via a reduction from 2D bin-packing? If so, how do you prove this? If not, then just saying that you can solve this using bin packing says nothing about the complexity. – Homophile

@Homophile Good point. Since I don't have all the constraints, I cannot claim that it's "definitely NP hard". And even if I did have all the constraints, it's hard to prove that something is NP hard :) I still think it's most likely NP hard though. – Ironclad