Thoughts On Algorithms, Geometry etc...

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 failed to spot it in this book because I used semicircle, disk and half-disk as search keys whereas the authors use 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??

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.

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.

Friday, November 18, 2016

On Elliptical Containers

The problem:

Given a convex 2D region C, find the ellipse of least perimeter containing C.

Special case: Experimentally, we saw that even for a given triangular region, the minimal perimeter elliptical container is not in general the same as the minimal area elliptical container (the latter is of course, the well studied Steiner ellipse).

Is something known about the center and orientation of the least perimeter containing ellipse for a given triangle? And what about such an elliptical container for a general convex region? And of course, the question can be generalized to higher dimensions.

There is a vague hope that despite the absence of a closed form expression for ellipse perimeter, one could find the dimensions of the containing ellipse with minimum perimeter. For example, one can compare the perimeters of two equal area ellipses without knowing the actual perimeters by just looking at the major and minor axes; so....

Note: It is not hard to see that if the container is a rectangle, the least area rectangle container and least perimeter rectangle container of a given convex region need not be the same (for an example, consider the "square being trimmed" example given in last post). It looks conceivable (not sure though!) that both such rectangular containers can be found by the rotating calipers method. However both the least area and least perimeter elliptical containers need not be aligned with any of the edges of the convex region C so a variant of such an approach might not work.

However, here is a bit of guesswork: For any fixed convex region C and an angle alpha measured w r to any fixed reference direction, we have a unique ellipse of minimal perimeter aligned at angle alpha and containing C. As C is kept fixed and alpha varied, the parameters of the minimal perimeter containing ellipse aligned with alpha - {its center, the axes a and b, its perimeter} - all appear to change continuously. And the number of times the derivative w r to alpha of the perimeter changes sign appears limited by the number of sides in the convex region. So a well-defined global minimum of this perimeter should exist.

Note added on December 3rd, 2016:

Experiments were done to guess the center or the foci of the least perimeter elliptical containers of isosceles triangles. All findings so far are negative. The center of the least perimeter elliptical container of a triangle is in general NOT the centroid, NOT the orthocenter,... The foci of this container also could not be pinned to any of the known special points of the triangle. These are only numerical observations.

Wednesday, November 02, 2016

Wrong Conjectures

Recording two conjectures and counter-examples.... Thanks to Prof. Erich Friedman.

1. Given any convex region C. Let R be the largest area rectangle that can be drawn inside C and R' the smallest area rectangle that can be drawn containing C. Claim: R and R' necessarily have the same alignment (same axes of symmetry). Note: A wider version of this claim could be stated generalizing from rectangles to any other convex shape with reflection symmetry.

Counter-example: Take a square, and shave off opposite corners at a 45 degree angle. For small cuts, the exterior square and interior square are optimal. For large cuts, a 45 degree rectangle is better. It would be a big surprise if the two phase transitions took place at exactly the same point.

And indeed, as can be checked numerically, the two phase transitions DO NOT happen at the same point.

o 2. Claim: The rectangle with largest perimeter that can be drawn inside any convex C is either degenerate (zero area, only length) or the same as the interior rectangle with highest area. Similarly, from among the rectangles containing C, the one with the least perimeter is the same as the one with least area. Note: This claim could be generalized from rectangles to ellipses or any other regions with reflection symmetry.

Counter: This claim is easily shown to fail by considering rectangles inscribed in any given ellipse. The inscribed rectangle with max perimeter is not usually the one with most area.

As for max containing rectangles, by considering the counterexample for claim 1( the progressively shaved square), we see that that for a certain stage in the shaving, the the 45 degree outer rectangle has less area but the outer square has less perimeter.

Note: Also tried to find CONTAINING ellipses with least area and least perimeter for a family of isosceles triangles all with same fixed apex and altitude but different bases. The least area containing ellipses of these triangles all have the same center (the centroid, which they all share anyways) - indeed these are their Steiner ellipses - but the centers of the least perimeter containing ellipses vary.