Thoughts On Algorithms, Geometry etc...

Wednesday, November 07, 2018

Non-Congruent Tilings of the Plane - a bit more

. The basic question of whether one can tile the plane with mutually non-congruent triangles all of equal area and perimeter has been answered in the negative by Kupaavski, Pach and Tardos (as already noted in this earlier post here: )

Another question: If one looks for tiling the plane with non-congruent triangles of equal area and equal diameter (diameter of a triangle is its longest side) what happens? I the answer is in negative, can the plane be tiled with convex pieces of equal area and diameter with no constraint on the numbers of sides? And what about other combinations of quantities maintained constant over the mutually non-congruent tiles?

I don't know if an answer to these questions follows naturally from the above mentioned paper. A few variants of the basic question answered in the above-mentioned paper had been recorded in earlier posts here (especially this post) but if I am not mistaken, the "area & diameter constant" case wasn't mentioned.

Saturday, November 03, 2018

On Aperiodic Packing

In continuation of this this earlier post here:

a simple question:
"Are there convex 2D shapes which cannot tile the plane and for which the best packing fraction is achieved by an aperiodic arrangment and not by a lattice one?" (the question can be posed for general -non-convex shapes as well).

If such regions exist, which among them shows max difference in packing fraction between its best lattice and best aperiodic pack?

Mathworld says: "Gauss proved that the hexagonal lattice is the densest plane lattice packing with unit circles and in 1940, L. Fejes Tóth proved that the hexagonal lattice is indeed the densest of all possible plane packings."

Note: Fejes Toth has proved that a lattice arrangement is the best packing for any centrally symmetric shape. So one has to look beyond such shapes for answers to our question.
And just as aperiodic packing, one can ask about shapes for which aperiodic covering beats lattice covering.

Saturday, October 27, 2018

Variants of the Kissing Number Problem

Let me record two variants of the famous kissing number problem that has a history going back at least to a debate between Newton and Gregory. I don't know if these questions have been explored.
Note: On this page are a proof that the kissing number of squares is 8 and an informed guess that the kissing number for unit cubes is 26 (no full proof of latter statement):

Arrange the least number of unit spheres touching a central unit sphere (call this unit sphere S) such that no more unit spheres can touch S. In 3D, the answer appears to be 4 unit spheres with their centers at the vertices of a regular tetrahedron and all touching S. What about higher dimensions?

Note inserted on October 28th, 2018: This problem is the same as 'blocking'. It was first attacked at least 20 years ago and features in 'Research Problems in Discrete Geometry by Moser, Brass and Pach. Just that I couldn't find the right search key. So, what follows here on cordoning are notes to myself

Remark: The question can easily go over to other convex shapes (cubes, tetrahedra,...) and dimensions.

In 2D, a unit circle can be cordoned by 4 unit circles; and a unit square can be cordoned by a minimum of 4 squares thus:

A 3D unit cube can be cordoned by 8 cubes. Indeed, view above cordoning layout of squares as a layout of cubes all lying on the XY plane and viewed from +Z with the central cube centered on Z axis. Shift the 4 surrounding cubes half unit in +Z direction. Then add another layer of surrounding cubes directly below the quartet shifted upwards. Now, the central cube can be touched only by a unit cube approaching it vertically from above or from below - all other directions of approach are blocked. And these two remaining directions can also be blocked by tilting the cubes already placed in the two layers slightly towards the Z axis by rotating them about the edges of the central cube they are touching. Of course, there may be better cordoning schemes and I don't know them.

If the central unit sphere S is a source of light, arrange a least number of opaque and perfectly absorbing unit spheres around it such that no light is visible from any far off point.

Note inserted on October 28th, 2018: This problem too is fairly well explored by experts. So, only the last bit of this post, 'further questions' might have (if at all) something of interest to experts.

As before, the question can easily go over to other convex regions (cubes, tetrahedra,....) and to dimensions other than 3. In 2D, although the kissing number of a unit square is obviously 8, we see that five unit squares are enough to screen a unit square:

Note: For circles, the kissing number is 6 as is the screening number - this looks obvious.

In 3D, the kissing number of spheres is, very famously, 12 but I don't know if the best way to screen is to form a possible best kissing arrangement and plug the gaps with more spheres.

On the best way to screen a unit cube:
One can build on top of the screening configuration for squares shown above and achieve a screening of a unit cube with 13 unit cubes. Indeed, think of the screening squares as a view from above of an arrangement of 5 cubes around the central yellow one with all cubes resting on the XY plane. Now, the yellow cube can be seen only from above or below. See picture below.

Now, an additional layer formed by 4 cubes could be put above (dotted squares in picture above) and another such layer below to totally screen the yellow cube; so we have a screening with 5+4+4 = 13 cubes.
But I have no proof of optimality for this screening arrangement. Looks like one can do better.
Note: If one goes to non-convex objects, one can have shapes screenable by 3 copies of themselves, at least in 2D.
Further Questions:
Note that these questions can be stated in any dimension.
1. Is the sphere (or maybe ellipsoids below some critical eccentricity) the worst 3D region for screening - ie it needs most opaque copies to screen? Which convex shape has the least screening number?
2. Likewise, is the sphere the best shape for cordoning - ie it needs least copies to cordon (maybe there are equally good shapes but none that is better)? And which convex shape needs max copies to cordon?
3. It appears that the units used for the best screening need not all touch the central unit. While building the best cordoning around any given central convex shape, do the cordoning units all necessarily touch the central unit?

4. One also thought of both these questions with the following additional constraint: the copies of the central body (call this S) to be put around S all need to be identical up to translations (iow the 'blocking copies' should all have same orientations).
For the questions thus constrained, will the optimal answers to both (least number of blocking copies) be necessarily achieved when the common orientation of the blocking copies is identical to the orientation of central copy S ( ie no other common orientation of blocking copies can beat it)? If so, does this property hold in all dimensions?

Friday, October 05, 2018

The Least Perimeter Triangle Containing a Convex Region

Sometime back, I posted an article at arxiv on 'oriented' convex containers of convex regions:

Among the issues mentioned there, the least area and least perimeter isosceles triangles that contain a given convex region is, as far as I know, yet to be fully resolved.

In that article, I had not touched upon the issue of finding and characterizing the smallest general triangle that just contains an input convex region. Here, 'smallest' could mean least area or least perimeter. As I found out recently, there are papers by Klee and Laskowski and by O'Rourke et al that date from 1980s which study and solve the question of least area triangle container of a given convex polygon.
However, finding the least perimeter triangle containing a given convex region is probably not yet done (to my knowledge). Here are some preliminary thoughts on this question. Note: I shall update or correct with proper date stamps (or if need arises, junk) this post as I learn more.

As given in the paper by O'Rourke and others mentioned above, the two key properties that characterize the least area triangle container (call this T) of a given convex polygonal region R are:

1. The mid point of each side of T is on R

2. At least one side of T is flush with R (ie is a side of T is a superset of a side of R).

There may be many triangles that has these properties vis-a-vis R and each is a local minimum in area of containers. One of these is the global minimum.

Note inserted on October 10th 2018:
The problem of min perimeter triangle container is indeed well studied as I just learned. The first bit of major progress was made by DePano back in 1987. He proves the following basic lemma: The least perimeter containing triangle of a convex region R has at least one side flush with R. Using this lemma, efficient algorithms to find the container too were established. So most of this post are only notes to myself except perhaps, the last bit below named: "Further Questions"

Consider the following figure:

ABC is a right triangle. M1, M2 and M3 are midpoints of its sides. Then a convex region (drawn in thicker lines; call this region R ) is shown inscribed in ABC with the following properties.
- An edge of R is flush with the base of ABC and contains the mid point of the base. Another edge of R is flush with the altitude of ABC and contains its mid point.
- Another edge of R, PQ is flush with the hypotenuse of ABC and contains the mid point M2 of the hypotenuse as shown. Above Q (going CCW), the boundary of R deviates inwards from the boundary of ABC.

Now, from what one understands from the above mentioned results, ABC is the least area triangular container of C.

Consider another right triangle AB'C': this has slightly less altitude than ABC and slightly more base and its hypotenuse only touches R at the end point Q of the edge of R that is flush with ABC. Obviously, AB'C' is another triangle that contains C.

Now, if ABC is chosen to have narrow base, it is seen experimentally that the newly constructed right triangle AB'C' has less perimeter and more area than ABC. So we conclude that the least perimeter triangle that contains a given convex region is not in general the same as the least area triangle container
Note: We don't say AB'C' is the least perimeter triangle container of R. We only note it is better than ABC.
Now, we ask whether the least perimeter containing triangle has the above properties of the least area containing one. Consider this slightly changed figure shown below:
In this, ABC is unaltered and R has been infinitesimally changed from figure 1 so that it only touches the base and altitude of ABC at the mid points of these sides of ABC. PQ has been retained as a straight edge of R and is flush with the hypotenuse of ABC as before. Now, it looks conceivable that ABC remains the least area containing triangle of the altered R; even if there is another containing triangle with slightly less area than ABC, it appears to have more perimeter (ie is longer and thinner) than ABC. So, the same AB'C' is a lower perimeter triangular container or R than the least area container.
So, we guess that the min perimeter triangular container
- need not have mid points of its sides on the contained polygon
- need not have any side of it flush with the contained polygon.
Further questions:
Which shape of R is such that its least area containing triangle and least perimeter containing triangle have greatest difference in their areas and perimeters?
More precisely, there are two questions:
- which shape of R maximizes the ratio between the area of its least perimeter triangle container and the area of its least area triangle container?
- Which shape of R maximizes the ratio between the perimeter of its least area triangle container and the perimeter of its least perimeter triangle container?
I am not quite sure if the answer to both these questions is the same shape.
The question of least perimeter quadrilateral containing R too seems not studied; the quad of least perimeter containing R may well be different from the quad of least area that contains R.

Friday, September 28, 2018

'Almost Right' - Fair Partitions and Non-Congruent Tiling

An interesting discussion took place around the 23rd minute of this lecture by Gabor Tardos:

The topic of the lecture: The impossibility of tiling the plane with pairwise non-congruent triangles all of the same area and perimeter.

A question came up from the audience: What if we retain the mutual non-congruence but instead of equality, allow both area and perimeter to be all within a few percent of one another?

A nice and simple answer too came up instantly: Take any tiling of the plane into identical triangles and simply perturb each vertex in the layout slightly - each in a different way. Intuitively, this achieves a non-congruent partition into triangles with areas and perimeters close to one another within any arbitrarily chosen bound. So, the impossibility happens only when one asks for areas and perimeters of the mutually non-congruent triangles to be precisely equal; allow both quantities even a slight but finite epsilon margin and there seem to be infinitely many ways to get the job done.

Concluding that discussion, Prof. Tardos remarked: "if you think two minutes, you can come up with a similar nice question which won't be easy at all to solve!"

There seems to be a fundamental difference between the above question and fair partition / spicy chicken - cutting a convex region into n convex pieces of same area and same perimeter (proved possible for any n only very recently, after over a decade of efforts). For fair partition, it does not look anywhere near obvious that if we allow the pieces to have areas and perimeters to differ by some epsilon fraction, such an 'approximately fair partition' can be done easily.

Well, I don't really know if the difference between these problems is a fundamentally interesting one!

Wednesday, September 26, 2018

Beyond Rep-tiles

A rep-tile is a shape that can be cut into smaller copies of the same shape -

Doubt: Is there a triangle T such that a certain number of T's can tile a triangle dissimilar to T?

Trivial example: 2 copies of right triangles tile an isosceles triangle dissimilar to the right triangle. An equilateral triangle is tiled by 3 mutually identical triangles which are not equilateral.

So the question is whether there are more non-trivial such examples, say, a triangle that can be tiled by 5 or 6 or n (but not less) mutually identical triangles that are dissimilar to itself.

Is there any quadrilateral that can tile a quad that is dissimilar to itself?

Again there is the trivial example of two copies of a trapezium with two angles = 90 degrees together forming a rectangle. Again, are there more non-trivial examples?

An equilateral triangle can be cut into 3 identical quadrilaterals that meet at its centroid. So one can ask, is there any triangle that allows partition into some other finite number of identical quadrilaterals.

And these questions have obvious 3d generalizations. Trivial examples can again be made by lofting the 2d trivial examples into prisms. And a regular tetrahedron can be cut into 4 identical tets that are dissimilar to the regular one.


A doubt about a theorem by Kantarovich:

Theorem (as I understand it): Given any planar convex region P and a set of n points, we can shoose weights for each point such that a weighted Voronoi partition of P with these points as nuclei is an equipartition. And if these points are moved continuously, the weights for which they yield an equipartition also change continuously.

Doubt: Is it guaranteed that if one insists all weights to be 1, there is a set of nuclei that gives an equipartition? Do Voronoi partitions with such special sets of points have any further properties?

Wednesday, September 05, 2018

Doubts on Covering

Consider trying to cover the largest scaled copy of a region C with n instances of a fixed tile T (iow, we were asking how big a circle or square or... (C) could be covered with n copies of an equilateral triangle of unit side or unit square square or unit circle .... (T) (see Erich's Packing Center for several families of such questions: (

Question 1: In the best covering layout for a given C with n T's, consider regions where where more than one T unit overlap. The observation is that if T is non-convex, the best layout could have regions where an arbitrarily large number of T units overlap (see below).
However, for the case when T is convex, no known best covering layout (as seen at say, Erich's Packing Center), seems to have regions where more than 3 unit Ts overlap. [Eg: see this page of covering largest possible squares with n unit circles: . For n = 3, 8 , 9, 11, there are regions where three unit circles overlap but nowhere where more than 3 overlap]. Is this a provably strict bound?

Note 1: An example of the non-convex case mentioned above:

In above picture, the shaded non-convex region is the tile T and C is the circle. If the angle of the 'fan' portion of T divides 360, a suitable number n of unit Ts can cover the big circle. Then the 'core' of the big circle could have n T's overlapping. Note that the two circles are concentric and the inner one - core - is quite small (the radius of this core being much less than the length of the arc portion of the tile that is shown lying along the big circle periphery; iow, the core portion of each tile is a lot smaller than shown in the figure). And the same n units don't seem to be able to cover any bigger circle.

Note 2: One could also go to higher dimensions and ask if there is an upper bound on the number of tiles (which are 3d regions now) that can overlap in some part of space when n tiles cover a convex region C of maximum volume. And of course, other (non Euclidean - geometries.

Question 2:

'Erich's Packing Center' has lists of coverings such as 'equilateral triangles covering squares, squares covering circles and so on...'

Could we have any intuitive 'large scale' results such as (say):

a. "For any n, among all unit area triangular tiles of unit area, the equilateral triangle tile is the the one such that n units cover the largest square" . And if this claim is invalid, is it that for every n, that the triangular unit such that n units thereof covers the largest square has a different shape?


b. "For any n, among all unit area rectangles, the square is the one such that n unit squares cover the largest circle"

.. indeed many such claims can be made but how many are valid?

Note (October 19th, 2018):
A further question could be posed:
Given a set of convex regions (call them covering tiles) with no constraint of equality among them and one tries to arrange them so that they together cover the largest (in terms of area or perimeter) convex region. Is there any upper bound on the number of covering tiles that can overlap somewhere?

The answer appears to be negative. Consider the following figure:

8 convex regions together cover a square. 4 of them are mutually identical isosceles triangles and at the center is a small region where these 4 covering tiles all overlap (the other 4 tiles are quadrilaterals as shown). Now, it appears that there is no convex region larger than the square that can be covered by this set of 8 covering tiles.
The construction appears generalizable to hexagons covered by 12 regions with 6 of these regions (all isosceles triangles) overlapping at the center, octagons covered by 16 tiles of which 8 overlap and so forth.

However, when the covering tiles have to be identical, one still has no example where more than 3 of the covering tiles overlap when together covering the largest possible convex region.