Thoughts On Algorithms, Geometry etc...

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.

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?