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?

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.

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₀.