1
$\begingroup$

A contact between two planar convex regions obviously happens either along a line segment or at a single point.

Question: Given a planar convex region $C$ and a number $n$, we need to lay out $n$ copies of $C$ (units) on the plane such that the total number of contacts among pairs of units $C$ is maximized.

For any $C$, will forming a layout of $C$ units such that the convex hull of them all has least area work? I am not sure. I have no counter example either. It is conceivable that the question needs to be solved in a case-by-case (each case being a specific shape of $C$ and a value of $n$) manner like packing.

Note 1: As pointed out in the answer below, minimizing area of convex hull is not a very good way to cluster the units as closely as possible. A better way might be to minimize perimeter or diameter of the hull of the layout.

Note 2: If, say, for the unit circle, the problem admits an algorithm that works for all values of n, it would be nice.

The question goes over to 3D and above. It seems less likely that a 'hull-compacting' layout will work for higher dimensions. One can also ask what happens in non-Euclidean geometry.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The left shape below has $3$ contacts (circled) "between pairs of units" and hull area $> 3$, while the right shape has $2$ contacts and area $3$. So minimizing the hull area does not always maximize contacts.

Contacts

(After OP's edit.) I don't think minimizing perimeter will maximize contacts, either. Here is an idea for a proof (but not a proof). The left image below show the optimal packing of $10$ congruent disks in a circle, from this Wikipedia article. I count $12$ contacts. Cannonball packing $5$ disks in two rows has many more contacts---$17$. The circumscribing circle has a much smaller circumference than the perimeter of the bounding rectangle of the two rows of five disks. It seems plausible that using the convex hull instead would not change the situation: the perimeter of the hull of the disk packing on the left is likely smaller than the hull on the right. But I emphasize I did not verify this through a careful calculation.

CirclePacking

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thanks. What I had in mind was whether placing the units in the most thickly clustered layout would actually maximize the total number of contacts. Have tried to improve things in an edit to the question. $\endgroup$
    – Nandakumar R
    Commented Feb 10 at 17:15
  • $\begingroup$ Guess I now see your main point: just trying to minimize the perimeter or diameter of the hull for n units isn't always v good - indeed, one might get into configurations where a 'central unit' won't have any contacts at all (as in erich-friedman.github.io/packing/cirincir for example n =8 or 9)! $\endgroup$
    – Nandakumar R
    Commented Feb 11 at 5:15
  • $\begingroup$ One last guess would be a greedy approach: start with a central unit, put as many units as possible in contact with it and put each new unit in contact with the already formed layout at least possible distance from the center. If this also fails, one might have to reconcile to a case-by-case approach to the question. $\endgroup$
    – Nandakumar R
    Commented Feb 11 at 5:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .