7
$\begingroup$

Let $S$ be a certain family of geometric objects (e.g, the family of unit squares).

The kissing number of $S$ is the maximum number of nonoverlapping elements of $S$ that can touch one element of $S$. See here an example where $S$ is the family of unit-squares: The kissing number of a square, cube, hypercube?

Define the overlapping number of $S$ as the the maximum number of nonoverlapping elements of $S$ that can overlap one element of $S$.

Obviously, the overlapping number is not larger than the kissing number since, if the central object has to be overlapped (not only touched), there is less room for the peripheral objects.

What else is known about the relation between the kissing number and the "overlapping number"? In particular, is there any bound on the ratio: kissing-number/overlapping-number?

EXAMPLE: When $S$ is the family of axis-parallel unit-squares, the overlapping number is 4 and the kissing number is 8. So the ratio is 2.

$\endgroup$
2
  • 3
    $\begingroup$ Is it obvious that the overlapping number cannot exceed the kissing number no matter how strange the family $S$? $\endgroup$ – Ben Barber Aug 12 '15 at 15:31
  • 1
    $\begingroup$ @BenBarber you are right... it is not obvious. Perhaps it is obvious for convex objects. $\endgroup$ – Erel Segal-Halevi Aug 12 '15 at 17:28
7
$\begingroup$

Even for a set almost the same as the one you mention in your question, unit squares but with the four corners removed, the overlapping number is larger than the kissing number. Only six cornerless squares can kiss another cornerless square, because kissing can only happen along the sides of a square, and if the kissed square has two kissing squares on one of its sides then it must have only one each on the two adjacent sides. However, seven nonoverlapping cornerless squares can overlap a central cornerless square:

enter image description here

$\endgroup$
3
  • $\begingroup$ Beautiful, thanks! So I have to add a closedness condition. $\endgroup$ – Erel Segal-Halevi Aug 14 '15 at 5:33
  • 2
    $\begingroup$ @ErelSegal-Halevi Would a closedness condition help? Wouldn't same construction works for a corner-clipped square? $\endgroup$ – Yoav Kallus Aug 14 '15 at 12:31
  • $\begingroup$ @YoavKallus you are probably right. So, even in the simplest case of convex, closed figures, the overlapping number might be larger than the kissing number. $\endgroup$ – Erel Segal-Halevi Aug 14 '15 at 12:42
8
$\begingroup$

Contrary to your claim, the overlapping number $N$ can exceed the kissing number $K$. Moreover, there exists some fixed value of $K$ for which $N$ can be arbitrarily large.

This is a sketch of a proof, which I haven't attempted to make rigorous because it would be incredibly tedious to do so.

We shall define an $N$-nematode to be a compact subset defined in polar coordinates by:

$$ \varepsilon \leq r \leq 1 $$ $$ f(r) \leq \theta \leq f(r) + \dfrac{2 \pi}{N}$$

where $f$ is a smooth function, and $\varepsilon > 0$ is small.

A nematode

(It has a small ball of radius $\varepsilon$ removed from the centre, which you can't see in the diagram because $\varepsilon$ is microscopic.)

Just to check that you've understood my description, an $N$-nematode has area $\pi (1 - \varepsilon^2) / N$.

Clearly, $N$ $N$-nematodes can coexist in a 'family', where each nematode touches two others, and their non-overlapping union is the entire annulus. This time, I've made the $\varepsilon$-hole visible:

family of nematodes

Now, provided we make the nematodes really pathological (for example, if the function $f$ violently oscillates sinusoidally between $\pm \Omega^7$ a total of $\Omega^{13}$ times, where $\Omega$ is the reciprocal of $\varepsilon$), then a nice property emerges. Specifically, the centres of any two non-overlapping nematodes must be either distant (greater than $2 - \varphi$) or incredibly close (within $\varphi$ of each other), where $\varphi \ll \dfrac{\varepsilon}{N}$. Basically, nematodes are either disjoint in the way that discs are, or are almost concentric.

So in any arrangement of non-overlapping nematodes, the nematodes cluster into sets of cardinalities $\leq N$. Now, for a given nematode $\nu$, we can easily bound the following quantities:

  • The number of nematodes in the same cluster as $\nu$ which touch $\nu$ (bounded above by $2$);
  • The number of different clusters, members of whom can be touched by $\nu$ (bounded above by the maximum number of points that fit into a radius-$(2 + 2 \varphi)$ disc such that no two are within a distance of $2 - \varphi$, which is certainly $7$);
  • The number of nematodes within another cluster that can touch $\nu$ (certainly $3$ will suffice, by some sophisticated argument concerning the convex hulls of clusters).

This gives a universal bound (independent of $N$) on the kissing number $K$ as $2 + 7 \times 3 = 23$. And we can easily get an overlapping number of $N$ by arbitrarily and effortlessly dropping a nematode $\nu$ onto a family of $N$ nematodes, where the distance between the centre of $\nu$ and the centre of the family is $1$.

The result follows.

$\endgroup$
1
  • 1
    $\begingroup$ I haven't read the proof yet because I am busy staring at the beautiful nematodes... they look as if they are moving. $\endgroup$ – Erel Segal-Halevi Aug 14 '15 at 5:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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