Thoughts On Algorithms, Geometry etc...

Tuesday, June 14, 2016

Non-Congruent Tiling - an Ongoing Story

News Update: Dirk Frettloh has written a preprint on some interesting fresh work of his and consolidating whatever is known on the non-congruent equipartition problem here:

Recording some speculations and thoughts on similar lines:

1. It appears that a plane cannot be tiled by mutually non-congruent, equal area rectangles if the following constraint is applied: The thinnest of the rectangles has length less than twice its thickness. The proof for this goes on similar lines to the proof that with near equilateral triangles all with same area and perimeter, the plane cannot be tiled (mentioned in an earlier post). One is not sure if relaxing the constraint partially (ie with some upper bound on the length to width ratio) will enable such a tiling.

2. Can the plane be tiled with non congruent right triangles all of the same area? (With equal area rectangles, one can have spiral arrangements; with right triangles, one is not sure)

3. Can the plane be tiled with non congruent right triangles all with the same hypotenuse (ie all those right triangles inscribable in the same semi circle)? Can one manage with non congruent triangles with same area and same longest side?

4. Can the plane be tiled with equilateral triangles, all of different sizes? More generally, can a plane be tiled by non congruent but mutually similar triangles? These questions let go of the equal area requirement.

Note 1: As was mentioned in an earlier post (, is is not very hard to tile the plane with squares all of different sizes. Method: a way to dissect a square into 21 squares all of different sizes is known. Do this to a unit square, then along side this dissected unit square, patch another unit square, then build outwards a Fibonacci spiral of squares of increasing size. Of course, this will need arbitrarily large squares. See the Wiki article on 'squaring the square' for details.

It looks very likely that *any* such tiling of the plane with unequal squares has to have either arbitrarily large or arbitrarily small squares - even if we use squares of irrational side. Not sure of this! At least as shown in the Wiki article mentioned above, we can have a lower bound on the size of the squares used.

Note 2: With equilateral triangles, such a tiling seems doable but unlike in the square case, a lower bound on the size of the tiles may not exist. Not sure!

5. CAn the plane be filled with rectangles none of which share either dimension? This appears doable with spiral arrangements starting with a Blanche dissection. But then, what is one wants some upper bound on the length to width ratio?

Shall update this page as answers come up...

Thursday, January 07, 2016

Tiling - Grading Non-Tiles

Basic intent: In addition to classifying polygons as those that can tile the plane and those that cannot, further probe the non-tiles and grade them in their ability to progress towards a full tiling.

I recently came to know about the Heesch problem. Basic question: which are polygons that can neatly surround themselves with copies but fail to tile the entire plane? Generalization: Which polygons can surround themselves 2,3, n times but fail to tile the plane? The number of 'coronas' a polygon can form around itself with copies of itself is its Heesch number.

Eg: A regular pentagon has Heesch number 0, it cant surround itself neatly even once.

The following polygon has Heesch number 1: Take a regular hexagon with side a and stretch 3 alternate sides to a larger length b (so the edge lengths are a,b,a,b,a,b) keeping all angles at 120 degrees. It can surround itself once with copies of itself - to see this just reflect the polygon about all its edges. See figure below. But it cannot surround the resulting layout neatly with copies of itself. (Thanks to Profs. Roman Karasev and Arseniy Akokpyan for telling me about this polygon).

Heesch himself had found a convex pentagon which has Heesch number 1. Details are here:

I dont yet know about convex polygons with higher but finite Heesch numbers.

One could try another tack to classify convex polygons which fail to tile the plane but are better than obvious non-tiles. The Heesch problem is about repeatedly surrounding a central tile with copies. So we tried another topology - tiling the plane by patching together 'walls' of polygons.

Let us define a WALL as a *simply connected* set of points formed with infinitely many polygonal regions and dividing the plane into two disjoint regions A and B such that the distance of any point P_A in region A to any point P_B in region B has a finite lower bound ( intuitively, A and B should be clearly separated by the wall and the wall should have no cavities inside it).

Given a polygon P, we could form a wall W1 out of copies of P, then form another wall W2 with copies of P, then see if the two walls can be 'patched' to form a thicker wall W (W1 and W2 could be identical). And if this process can be continued indefinitely, P can tile the plane. We could call W1 and W2 to be 'patchable' walls. We could say a wall has thickness t if it can be 'sliced' into t walls.

It is easy to see that copies of any convex polygon P can form walls in infinitely many ways. But for most polygons, even forming 2 patchable walls is impossible. For example, the hexagon with Heesch number 1 above can form 2 patchable walls .

The Heesch polygon (another convex polygon with Heesch number 1) too can form 2 patchable walls - resulting in a wall of thickness 2. In figure below, it is shown how copies of this tile can form a wall that is bounded below by an infinite straight line so an identical wall can be patched to this wall. But it appears that no further patching can be done on to the resulting 2- layer wall to form walls of higher thickness.

Question: Are there non-tiles which can form walls of thickness 3 (or in general n)?

Saturday, August 29, 2015

Another Convex Equi-partition Problem

Problem: To divide a 2D convex region C into a specified number n of convex pieces all of equal area (perimeters could be different) such that the total length of cuts used is (1) maximized (2) minimized.

Question 1: It appears that for maximum total cut length, the cut lines should not meet in the interior of C. A greedy approach (from C, first cut out a convex region with 1/n of the total area such that the separating cut is the longest possible, then repeat the same process on the remaining piece and so on until we have n equal area pieces) appears to give the optimal answer.

I have no proof or counter example for this greedy algo (note: don't even know a C and n where for max total cut length, the cuts do not all originate from the same point on the boundary).

Question 2: I don't know about minimizing the total cut length. Hopefully, work already done by experts on the Fair Partition front will help.

Update(4th Sept. 2015):

Learnt from Profs. Karasev and Ziegler that the minimizing the total cuts version of the question is most likely much harder and would require heavy machinery to attack.

Have been trying the apparently simpler N=3 case of the maximum-total-cut-length problem; ie. to prove/disprove the guess that the equal area partition into 3 convex pieces of any convex region using max cut length is such that the cuts DO NOT meet in the interior. No luck yet (Just a thought not carried to conclusion: maybe one can show for a convex region C the following function f is concave and so has its max value on the boundary of C: f is the max total cut length of an equipartitioning 3-fan radiating from each point in the region.}

One suspects that there is nothing special about the areas of pieces being equal. Even if the convex region is to be divided into convex pieces with areas in the ratio a:b:c:... using max total cut length, the cuts might again not meet in the interior.

The order in which the pieces are separated would impact the total cut length; a starting guess is: sort a,b,c... and greedily cut out pieces from the smallest area upwards But this need not achieve the most total cut length. Indeed, if the areas of 4 pieces to be cut from a circular disc are in the ratio 1:10:10:1, cutting out the 1's first would not maximize the total cut length it is better to cut out a 10 first. Likewise, separating off pieces in descending order of area would not work in general either.

Maybe one could do the following instead: Sort the areas required. Then from the given region C, cut out a piece with the smallest area (say a1) such that this piece has the highest possible perimeter. This act will give a piece of area a1 and two big convex pieces say C1 and C2. Now from either of C1 amd C2, separate out the next smallest area a2 and so on recursively - again, a greedy approach.

Note: And as usual, higher dimensional analogs of the question could be interesting - eg: a 3D convex region to be cut into convex regions of equal volume such that the total surface area of pieces is maximized/minimized. One can also examine the length of the new edges generated.

Update( 17th September 2015)

A bit of clarity (?) on the N=3 case of maximum-total-cut-length: Let some C be cut into three convex equal area pieces by a fan of 3 rays radiating from any interior point P. Let p_0 be the sum of the perimeters of the three resultant pieces.

Now, let A, B and C be the three points where the three equipartitioning rays from P intersect the boundary of C. Starting from each of these points A,B,C, we have a unique pair of rays which cut C into 3 equal area pieces. Let p_A be the sum of the perimeters of the 3 pieces resulting from rays starting at A. Similarly we have perimeter sums p_B and p_C.

One observes that for any position of P and any A,B,C (satisfying the equal area and convexity constraints), at least one of p_A, p_B and p_C is necessarily greater than p_0 (no neat proof of this bit yet). This would readily imply the total cut length cannot be maximized by a fan of 3 rays starting at an interior point (Note: Sum of the perimeters of the 3 pieces = perimeter of C + 2 X total cut length).

Saturday, August 08, 2015

Partition into Isosceles Triangles

Question: What is the best way to partition a given polygon into isosceles triangles?

What is known to us: One has an upper bound of 4*(n-2) isosceles triangles for any n-gon. Indeed, the n-gon can be cut into n-2 triangles and each triangle cut into 4 isosceles triangles.

And this bound appears tight - eg. consider the following n-gon, with vertices lying randomly spaced along two broad arcs as shown below. The two long inclined sides are much closer to horizontal than shown. It appears impossible to partition it into less than 4*(n-2) isosceles traingles.

But there are also polygons which can be triangulated into only n-2 isosceles triangles; so we suspect it could be an interesting algorithmic challenge to partition a given polygon into the least number of isosceles triangles.

What follows is based on Martin Gardner's 'New Mathematical Diversions':

Further question: What about partitioning a polygon into ACUTE isosceles triangles? Can any obtuse triangle be dissected into seven acute isosceles triangles? The answer is no. Verner E. Hoggatt, Jr., and Russ Denman (American Mathematical Monthly, November 1961, pages 912-913) proved that eight such triangles are sufficient for all obtuse triangles, and Free Jamison (ibid., June-July 1962, pages 550-552) proved that eight are also necessary.

Question: So, does one have a tight upper bound of 8(n-2) for the least number of acute isosceles triangles that result from partitioning an n-gon?

Wednesday, June 24, 2015

A Doubt on Rep-tiles

Golomb defines a plane figure to be rep-k if it can be cut into k similar but smaller copies. It is known that the only convex rep-2 regions in 2D are the isosceles right triangle and the rectangle with sides in ratio 1: sqrt(2).

Questions: Consider the analogous 3D situation. It appears there are no convex rep-2 3D regions. The closest to rep-2 that one could get is only a 'loft' of one of the above two 2D rep-2 regions in the z directions. This gives a prism which of which only a fraction of 1/sqrt(2) is covered by 2 similar scaled down prisms. Is this the best one could get in 3D (have no proof)?

If so, does the same setup generalize to higher dimensions? ie. can one say: the 4d convex region closest to being rep-2 is got by just lofting the above 3d prism (generated from lofting the 2d region) into the 4th dimension to have a 4D region with coverage only 1/2 by two self-similar 4d regions.

Moreover, we don't know if one discards convexity, there are 3d regions which are rep-2.

Update (July 17th 2005)

From Dirk Frettloeh, I got a nice example of a 3D 2-reptile - a rectangular box of dimensions 1, 2^(1/3), 2^(2/3). Two of them piled together gives a 2^(1/3), 2^(2/3),2 box. This is generalizable to n-reptiles in 3D.

Monday, April 13, 2015

On Inscribed Polygons

Basic Question: If two convex polygons P1 and P2 both consist of the same set of edges but in different order and are hinged at vertices and we deform both at their vertices to maximize the enclosed area, will both chains yield the same max enclosed area?

Answer: It is all on: There is a nice proof that the area of a polygon with hinged edges all of fixed length is a maximum if the polygon is inscribed in a circle. The number or even the order of edges does not matter. And yes, any closed and hinged polygonal chain can be deformed at vertices so that it becomes a cyclic polygon.

Further question:

Consider a 2D smooth convex figure C and a convex closed polygon P, both deformable as follows: The sides of P are hinged at its vertices and free to rotate but we require P to be planar and convex throughout any deformation at these hinges. On the other hand, only scaling is allowed for C.

Claim: Using the transormations specified above, we can always change P and C such that the final form of P can be inscribed in the final form of C ( ie all vertices of P lie on the boundary of C).

Remark: As of 13th April 2015, one doesnt know if the claim holds. It is likely to hold. Maybe any closed and hinged polygonal polygonal chain can be inscribed in the homothet of any smooth figure (not only smooth convex figures).

Sunday, February 15, 2015

A Packing Doubt

Let us call a connected set of points 'centrally symmetric' if there is a point P such that if V is a vector joining P to a point in the set, moving -V from P yields another point in the set. P is called the center of symmetry.

Question: In 2D consider the set of all centrally symmetric regions (not necessarily convex ones). Are there such regions for which the best packing of the 2D plane with copies of it is NOT periodic? If there are, which is the region with its optimal pack giving the greatest departure in filling fraction from its best periodic pack?

If the answer to the analogous question in 3D has a negative answer, the Kepler conjecture will follow as a corollary. So, since Kepler is nontrivial, there must be such connected 3D regions for which the best space filling arrangement is aperiodic. What of 2D?

This 2D question should have a known answer. Shall record it here when I find out.

Doubt: How much does one lose by way of packing efficiency if all centrally symmetric unit shapes are constrained to have the same orientation?


Partial Answer (April 2015)

It seems that if the rotations are not allowed, using only translations, then the best packing has to be a lattice packing. It is not clear if the rotations can improve the packing density for planar centrally symmetric sets. This is for convex 2D sets.

For non-convex centrally symmetric sets, here is an example due to Prof. Roman Karasev. It packs perfectly with rotations and rather badly without them.

Note: I saw in the Wiki article on Kepler conjecture that Gauss had proved the conjecture for regular arrangements of spheres in 3D. That could mean that for some other centrally symmetric 3D figures, the regular arrangment may not be the best. I know of no example though (not even non-convex shapes). I don't yet know of 2D convex regions for which non-lattice arrangement is better at filling the plane than the best lattice layout.