1
$\begingroup$

A related post: To place copies of a planar convex region such that number of 'contacts' among them is maximized

Basic question: Given two convex polygonal regions P and Q, to arrange the max possible number of copies of Q around a single P unit with all the Q's touching the central P with no two regions overlapping. Can an algorithm be found to solve any P and Q? The case of P and Q being the same could be interesting in itself.

Remarks: If one can think of the rotating calipers method as a polygon rolling on its edge along a plane, the present question seems like two gear wheels P and Q rotating while staying in contact.

A couple of variants:

  1. For a fixed convex P (say, a square) and a number n, to construct a convex Q with least number of sides such that n (but no more) copies of Q can be put around a central P and touching it. Will an equilateral triangle of suitable side suffice for any P and n?

  2. Given a number n (say 11), to find a convex P such that n (and no more) copies of P can be arranged around a central P and touching it. Guess: a suitable isosceles triangle might work for any n.

Note: The question has a natural analog in 3D. Further possibilities include insisting that the contacts between polygons be at exactly one point.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Shouldn't the first question be decidable by Tarski-Seidenberg? For given $n, P, Q$, express the configuration by a bunch of real parameters (subject to some equations for the rotations), and the touching and non-overlapping by more equations and inequalities. Then the existence of a solution is decidable. Of course, this is not going to produce a practical algorithm. $\endgroup$
    – Achim Krause
    Commented Jun 7 at 17:09
  • $\begingroup$ (sorry, of course this only gives an algorithm that decides whether $n$ copies of $Q$ fit around $P$ for given $n$, but since one can get an a priori upper bound from considering diameters and areas, one just needs to run it finitely many times to find the maximum $n$) $\endgroup$
    – Achim Krause
    Commented Jun 7 at 17:15
  • $\begingroup$ Thanks. Is checking whether an arrangement can be made for each n until the limit is reached an optimal algorithmic approach? Alternatively, can one find the max number of Q units that can touch each edge of P (each edge is a line segment) and then patch the answers of segments together (complications might arise from this patching)? $\endgroup$
    – Nandakumar R
    Commented Jun 7 at 18:42
  • 1
    $\begingroup$ No, none of this is optimal, everything I wrote just considers the abstract question of whether such an algorithm exists. $\endgroup$
    – Achim Krause
    Commented Jun 7 at 18:45
  • $\begingroup$ See my kissing-number comment below. $\endgroup$
    – Joseph O'Rourke
    Commented Jun 12 at 14:47

1 Answer 1

Reset to default
2
$\begingroup$

"the max possible number of copies of Q around a single P unit with all the Q's touching the central P."

Perhaps the problem is not stated precisely? This example seems to show that there might be no max---an infinite number of copies of $Q$ all surrounding and touching $P$ is possible.

QaroundP

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thank you. I had meant "no two of the regions overlap". Made an edit in the question. $\endgroup$
    – Nandakumar R
    Commented Jun 12 at 7:24
  • 1
    $\begingroup$ Ah, I see. You are asking a variant of The kissing number of a square, cube, hypercube?. Generalized to arbitrary convex $P$ and $Q$. "Kissing number" is the key search phrase. $\endgroup$
    – Joseph O'Rourke
    Commented Jun 12 at 12:31
  • $\begingroup$ Thanks for the pointer to this question - and its beautiful answer $\endgroup$
    – Nandakumar R
    Commented Jun 12 at 15:02

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