Thoughts On Algorithms, Geometry etc...

Tuesday, May 22, 2018

Going Hyperbolic

Let me state the broad question first: do some of the questions that were asked on these pages over the years have nontrivially altered answers if one goes to hyperbolic geometry from euclidean?

Specific examples:

1. Is it possible to tile the hyperbolic plane with equilateral triangles all of different sizes? In the Euclidean setting, the answer to this is that there will necessarily be arbitrarily small triangles in such a tiling (as has recently been proved by experts).

Note: On the Hyperbolic plane, we can have equilateral triangles (all angles equal, all sides equal) with every vertex angle value less than 60 degrees and there is a unique equilateral triangle with a given vertex angle.

2. Can one tile the hyperbolic plane with triangles all of same area and perimeter but mutually non-congruent (in Euclidean case, this question has recently been given a negative answer by Kupavski, Pach and Tardos)?

On the Hyperbolic plane, one needs to check if triangles with same area (same angle sum) and perimeter can be at all non-congruent and if so by how much.

Remark: The Hyperbolic plane has lots more room than Euclidean (for example, infinitely many ways to tile with regular polygons as opposed to just 3 in Euclidean) but does this also imply that the answer to question 2 might be "possible"? (By the same token, in elliptic geometry, things just possible in Euclidean might become impossible).

3. I have no idea if the the basic fair partition question - and the complete answer thereof recently found by Akopyan, Avvakumov and Karasev - goes over 'uneventfully' to hyperbolic.

Or the old congruent partition question. A preliminary finding there was: "A quadrilateral with all angles irrational fractions of pi but adding up to 2*pi cannot be broken into any number of mutually congruent pieces"

4. Or for that matter, if the question of 'fair and non-congruent tiling of the plane' (tiling the plane with convex regions of equal area and perimeter, but all mutually non-congruent and with no restrictions of their number of sides) becomes easier on the Hyperbolic plane - of course, I don't know even its Euclidean answer yet.

At a more fundamental level, I am yet to understand well how perimeter behaves on the Hyperbolic plane.

Update (May 27th 2018):

Here is another question that was recently put up as an addition to the two year old post 'Non Congruent Tilings - an Ongoing Story' ( Can the (Euclidean) plane be tiled with triangles that are similar to one another but all of different sizes? This question is irrelevant in Hyperbolic plane because similar triangles are automatically congruent there.

However, on the Euclidean plane itself, one could ask if there is any qualitative difference from the case of equilateral triangles with all having different sizes and the case of mutually similar but unequal triangles (the mutually unequal equilateral triangle case has been done as mentioned above). These questions can be generalized to quadrilaterals from triangles and to higher dimensions.

Update (June 9th 2018):

Adding one more question:

Find a set of rectangles all of same perimeter (let us call such rectangles isoperimetric rectangles) but with different areas which together form a neat big rectangle. Note that we are on the Euclidean plane now.

This question was attempted at and one ended up at:


It appears that no such rectangular layouts can be made with less than 7 isoperimetric tiles (we mean any rectangular layout, not only spirally arranged ones). There may be no layouts whe re (1) the big rectangle is a square (at least when the dimensions of the tiles are rational) or (2) with the number of isoperimetric tiles arbitrarily large (indeed, we know of no rectangular layout formed with more than 10 isoperimetric tiles). We do not yet know of any solution where the ratios between dimensions of the tiles are irrational.

One wonders how going to hyperbolic geometry would change things.

Note: A rectangle on the hyperbolic plane can be viewed as a quadrilateral with all angles equal but less than 90 degrees and opposite sides of equal length. But more than 4 rectangles need to be put around each internal vertex in the layout and that *might* mean that making the overall layout rectangular would be harder than in Euclidean case and perhaps impossible.

Aside: The 'rectangling the rectangle' problem with rational sides for tiles ( seems still open even on the Euclidean plane.

Updates/Corrections shall follow as and when I find out more from experts....

Tuesday, May 15, 2018

Double Lattices and Covering

One reads online that: A double lattice is the union of two Bravais lattices related to one another by a point reflection.

Moreover, a point reflection in 2D is the same as a 180 degree rotation.

Double lattices are often considered when looking for closest packs of the plane by a given convex region. For example:

To put things precisely: for packing copies of a convex region R in 2D, it is usually useful to have one lattice of translates of R and another lattice of translates of -R. This is a practical observation. Doubts: In 2D, what is so special about 180 degrees? Given a convex region R, if one considers two Bravais lattices of unit Rs related to each other by rotation about some other angle, is it guaranteed to give a poorer pack than some two lattices of R's related to each other by 180 degree rotation (the minus sign in -R)? And further, do double lattices being good candidates for 2D packing automatically make them good candidates for thinnest covering too?

Shall ask around and add to this post...

Thursday, April 19, 2018

Semicircle Packing

Although circle packing has been extensively researched, packing semicircles (half-disks is probably a more precise word) seems almost unexplored. Having hit upon this question, I searched but could find just one webpage - with a lament that there are no pages on packing semicircles(

A natural way to pack the plane with semicircles is by assembling pairs of them into circles and then packing the circles hexagonally. can one do better? maybe not. but not sure.

History (source Wiki):

Laszlo Fejes Toth "proved that a lattice pattern is the most efficient way to pack centrally symmetric convex sets on the Euclidean plane". Lagrange had earlier proved that "the highest-density lattice arrangement of circles is the hexagonal packing arrangement". Together we have the result that the best packing of circles in a plane is the hexagonal pack.

Doubt: Is it possible to generalize Fejes Toth's result to say (say!) "a lattice pattern is the best way to pack convex sets with an axis of reflection symmetry"? Such a deduction might take us to a quick resolution of the semicircle packing.

And of course, one can worry about packing quadrants, hemispheres (packing in 3d space), and then go from packing the entire plane to packing various special containers (one can visit, for instance, 'Erich's Packing center' with its hundreds of non-trivial variations on this problem)or to go from packing to covering .... !


Progress (April 21, 2018)

The question above was posed, back in 1971, by Fejes Toth himself. It is still not fully resolved (the 'pairing of semicircles' approach above is known to be clearly suboptimal). The problem is listed in section 1.5 of 'Research Problems in Discrete Geometry' (by Brass, Moser and Pach).

I had actually looked into this book but failed to spot it because I used semicircle, disk and half-disk as search keys - and the authors have used semidisk! The book doesn't mention the 3d analog of this question (packing hemispheres); is it that putting two hemispheres together to form a sphere and to form the hexagonal close-pack of them (Kepler!) will also be suboptimal in 3d?? 3D has lots more space than 2D (roughly speaking) so the hcp may be way off the mark.

Friday, January 12, 2018

Elliptical Containers

Note: This post reports some investigation done with help from K Sheshadri.

Question(s): Given an ellipse E, what is the least area (least perimeter) convex region for which E is the least area(least perimeter)ellipse containing the convex region?

As can be readily seen there are 4 questions in there - one for each combination: area-area, area-perimeter, perimeter-area, perimeter-perimeter. Out of these, since perimeter of the ellipse has no closed expression, so we first consider the case of least area ellipse container.

Note: The questions above can be generalized to higher dimensions.


The least area convex region for which a given ellipse E is the least area container is (almost certainly) any triangle for which E is the Steiner circumellipse. Indeed, there are infinitely many such triangles - all of them are inscribed in the ellipse and have their centroid at the center of the ellipse. It is a fairly straightforward calculation to show that the area of all these triangles is equal to 3*sqrt(3)*ab/4 where a and b are the axes of the ellipse. But it would be nice to find deeper arguments (we have none as of now) for "all triangles inscribed in an ellipse with centroid coinciding with the ellipse center have same area". We also find numerically that every point on the boundary of the ellipse is the vertex of one such inscribed triangle.

This appears to suffice: From the Mathworld article on Steiner circumellipse, the area of the Steiner ellipse of a triangle with area Delta is given by: A = (4pi)/(3sqrt(3))* Delta. This implies that for any triangle for which a given ellipse is the Steiner circumellipse should have the same area.


A side tour:

Guess: Among all 2D convex shapes without 3 fold rotation symmetry, the ellipse is perhaps the only shape such that every point on its boundary is a vertex of an inscribed triangle such that the centroid of the triangle coincides with the center of mass of the container shape. If true, this guess might follow from deeper reasons.

Remark: The guess is incorrect. Numerical checks confirmed that *any* triangle* has that property. Any rectangle too. Indeed, any triangle T appears to have a stronger property: If P is any point in a finite region around the centroid of T, every point on the boundary of T is the vertex of a triangle inscribed in T and with P as its centroid. One can ask if replacing T with any convex region will leave this property unchanged.

Then one sees that the property is not really hard to explain. Take any 2D convex region C and any point P1 on its boundary. Choose any point G within C such that if we extend directed line segment P1-G by a factor of 3/2, the new end point is still in the interior of C (for this G shouldnt be too close to the boundary of C). Let the end point of this extended P1-G be called M. Now, consider all chords of C that pass thru M. There necessarily is one of them such that M is its mid point (obvious). Let the end points of this chord be P2 and P3. It is easy to see that the centroid of triangle P1-P2-P3 (inscribed in C) is identical to G. Reason: G trisects one of its medians by construction and the medians of any triangle are necessarily concurrent.


The perimeters of triangles inscribed in a given ellipse with centroid at ellipse center show some variation but are quite close. Among them, the triangle with the least perimeter is (numerically), an isosceles triangle to which the major axis of the ellipse is the bisector of the apex angle. This triangle is also almost certainly, the least perimeter convex region for which the given ellipse E is the least area container.

Aside: Given an ellipse, every point on its boundary is also found (numerically) to be the vertex of exactly one triangle such that the *incenter* of the triangle coincides with the ellipse center. In this case, the family of triangles do not all have the same area or perimeter but the values are found to be quite close. One can ask: is there any other container (not ellipse) such that with every point of its boundary as a vertex, we have one triangle such that the incenter of the triangle coincides with the ellipse center? Same question can be asked with any other triangle center.

Moving on to the least area and least perimeter convex regions for which a given ellipse E is the least perimeter elliptical container: These convex regions are almost certainly not triangles - it appears that for any of the inscribed triangles of E for which E is the least area ellipse container, another containing ellipse E' with more area than E but with less perimeter exists.

Note: We can replace 'ellipse' in the basic question set with rectangle, right triangle or a host of shapes and generate several questions from the same ballpark. Some of them might have nontrivial answers. More on that soon.

Friday, December 01, 2017

On Triangles that Contain Triangles

One isn't sure if the following claims are valid. Hope to gain insights on these soon...

1. For any triangle T, the isosceles triangle with minimum area that just contains T necessarily has an angle equal to one of the angles of T.

2. The isosceles triangle with minimum perimeter that just contains T also necessarily has an angle equal to one of the angles of T.

Note: If one looks at the least area/perimeter right triangles that contain a given T:

It *seems* that if T is equilateral, the smallest area right triangle container is isosceles. But for general T, one needs to understand more. Perhaps this problem has already been studied. Shall update this bit soon.

Update-May 25th 2018: Both numbered claims above are not fully valid. They hold only when triangle T is acute. This and a lot more are in a forthcoming paper by Kiss and Pach.

Thursday, November 23, 2017

Non-congruent Tilings of the Plane - Update

The good news: A paper by Andrey Kupavskii, Janos Pach and Gabor Tardos has answered the question ( of tiling the plane with non congruent triangles of same area and perimeter - in the negative. Such a tiling cannot be done.

Here is their paper:

These are early days but one wonders if their approach (with suitable modifications) can be generalized to tell us if the plane can be divided into pairwise non-congruent quadrilaterals (or even convex regions) all of equal area and perimeter.

Note: Dirk Frettloh has shown in his paper a year and some back how to cut a plane into quadrangles all of same area and *bounded* perimeter but not same perimeter.

One could add a further constraint to the fair tiling with non congruent quadrilaterals - that of the vertex to vertex (vtov) requirement. There seem to be 'more than' aleph_1 different quadrilaterals of same area and perimeter and 'only' aleph_0 are needed to cover the plane so (guess) if the vtov constraint is NOT enforced, one can probably pick and choose the tiles carefully and manage.

We could also ask: is it possible to tile the plane with non congruent convex tiles all of same area and perimeter but with no further constraints on say, the number of sides of each tile? Such a layout could be called a 'non-congruent fair tiling of the plane'.


Sunday, December 25, 2016

Minimum Perimeter Elliptical Hull of a Triangle

This post continues the last post.

Problem: given a triangle, find the ellipse of least perimeter and containing it\

observation: it looks pretty clear that such a minumum perimeter elliptical hull ought to pass thru all three points of the triangle.


Just as a circle has three parameters (coordinates of its center and radius), an ellipse has 5 (coordinates of center, angle of orientation and the major an minor axes).

Sub-Question: given a triangle (3 points), we need to find ellipses passing thru all 3 and also being aligned along the X and Y axes (ie, its axes are parallel to the coordinate axes). this indicates that the locus of the centers of the possible ellipses will lie along some curve. what is this locus?

If the three pts are (x1,y1) (x2,y2),(x3,y3) and the center is (x0,y0) then they satisfy the eqns for ellipse:

(x1-x0)^2/a + (y1-y0)^2/b = 1

(x2-x0)^2/a + (y2-y0)^2/b = 1

(x3-x0)^2/a + (y3-y0)^2/b = 1

One could use mathematica to eliminate a,b from above and the collect the terms involving (x0,y0)- Thanks, Arun!

Since there is an x0y0 term and linear terms in x0 and y0, the locus seems to be a hyperbola.

In the above, we only found ellipses aligned to the coordinate axes. Intuitively, if we seek ellipses thru all 3 points and with arbitrary orientation, we should get a one parameter family of hyperbolas as the locus of the centers of all these ellipses – a stack of hyperbolas.

Now, for any point that lies on any one of this stack of hyperbolas, we have the center, orientation (given by which parabola from the stack we are on) and the three triangle vertices, we have an ellipse fully determined. For this ellipse, we could use the approximate expression known (or number crunching) to find its perimeter, then repeat for all possible ellipses and find the min perimeter.

Known facts: many of the centers of the triangle lie on the so-called Euler line. The incenter does not, in general. If we are looking for the containing ellipse with least area (not perimeter), its center is always the centroid of the triangle and the ellipse is called the Steiner circumellipse.

Speculation: The minimum perimeter ellipse containing the triangle appears to have its center necessarily inside the triangle. That the perimeter of an ellipse has no known closed form expression need not necessarily imply that we cannot say anything precise about the center of the minimum perimeter elliptical hull. It is conceivable that say, it lies on the line joining the incenter and circumcenter.