TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

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 or square or circle .... (T) (see Erich's Packing Center for several families of such questions: (https://www2.stetson.edu/~efriedma/packing.html)

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, but for the case when T is convex, no known best covering layout (as seen at say, the Packing Center), seems to have regions where more than 3 unit Ts overlapping. 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. 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.

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?

OR

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 valie?

Tuesday, August 14, 2018

Some Further Details on Fair Partitions...



A detail of the fair partition / spicy chicken problem. Thanks to Prof. Roman Karasev.

Question: In the paper by Karasev, Hubard and Aronov, (https://arxiv.org/pdf/1306.2741.pdf) theorem 1.3 says that "in 2D, a convex region can be divided into prime power number of convex pieces such that an absolutely continuous finite measure (eg. area) is equally divided and and one continuous functional ( eg: perimeter or diameter) has equal value for all the pieces". Qn: What will happen if we try to partition a 2D convex region into n convex pieces such that 2 continuous functionals have to have same value for all pieces - for example, diameter and perimeter should be equal for all convex pieces with no constraint on area? Eg: For n =2, this is possible from a simple continuity argument.

Note: The fair partition claim has been recently extended to all values of the number of convex pieces, not only prime powers.

Answer:

There is no guarantee that diameter and perimeter can be simultaneously equalized among pieces. For example, as the pair of the continuous functionals defined on the pieces you may take the $x$ coordinate of the mass center and the $y$ coordinate of the mass center. It seems unlikely possible to equalize the mass centers of the convex parts in a partition, right?

The crucial property used in the proof is that at least one of the functionals need to be "continuous on empty sets", that is tend to zero when a part is about to disappear, and at the same time be positive on parts with nonempty interior. Those are crucial properties we need from the area functional.

Further question:

One wonders if, from among continuous functionals defined on the pieces, there could be qualitative differences between those functionals that depend on coordinates (such as the x coordinate of center of mass of a piece - it depends on the coordinates and orientation of the input region) and those functionals that don't (such as perimeter or diameter of a piece).

-----------------

Another question: If one insists in a fair partition that the equal area and perimeter pieces ought to be also mutually non-congruent, what could be the implications? For N =2 and the input convex polygon a square, the 2 pieces are necessarily congruent so such a fair partition is obviously not always possible. But can one say more about situations and values of N where such partitions necessarily exist? Remark: Special cases of this question (eg: fair partition of square into 3 mutually non-congruent pieces, equilateral triangle into 5 pieces etc..) could be of interest.

I just learned from Prof. Karasev, that the solution space, of fair partitions (partitions into convex pieces of equal area and equal perimeter), at least when N is a prime power, is rather big, its dimension must be of order N. But it is not clear if the large number of solutions guarantee that for one of them the parts will be pairwise non-congruent.

-----------------

An unrelated question: Are there rep-tiles on the Hyperbolic plane?

Answer: Scaling makes no sense on Hyperbolic plane - among for example equilateral triangles, the bigger triangles have smaller angles than smaller ones. So, no way to build a scaled up copy of any tile with copies of the tile - the scaled up copy has smaller angles.

--------------------------------

Material added on 6th September 2018:

Questions:

1. If a convex 2D region is partitioned into N pieces such that the pieces all have the same perimeter (with no constraint on the area) such that we also minimize the total length of cuts, will the pieces necessarily be convex?

2. If the answer is "yes", does the same (convexity of pieces) hold if we equalize and minimize any other continuous functional over the pieces? And does such equalize+minimize operation on any other functional automatically yield pieces of equal area?

Note: Indeed, if one does an equal area partitioning into N pieces using least total length of cuts, the cuts could be arcs and so pieces are non-convex.

Here is an intuitive argument on question 1 above from Prof. Karasev:

---------------

If we have a partition into equal perimeter parts (call this perimeter P) that are not necessarily convex then we may first straighten the cuts. After that the parts become polygons, but still may have concave vertices. It then seems possible to push out the concave vertices so that the perimeter of the current polygon only decreases and the perimeters of neighboring polygons also decrease. Of course, there are technicalities in this process, but eventually we seem to end up in a convex partition into polygons with all perimeters at most $P$, but possibly not equal.

Then we try to move the cuts to equalize the perimeters and it seems that the maximal perimeter does not increase during this process, so we are likely to end up with equal perimeters no greater than the original value P. Since the common value of the perimeter is expressed in the perimeter of the total convex body and the total length of the cuts, the total length of the cuts will also be no greater in this convex situation then in the original non-convex one. In other words, given a partition of a convex region into convex pieces all with perimeters of pieces less than or equal to P but possibly unequal to one another (achieved by the previous steps) , it is very conceivable the pieces can be deformed to equalize their perimeter to a value below P and also keeping them convex.

---------------

Another question: For any convex 2D region, will the shortest perimeter bisector also be a fair bisector?

Answer: Not necessarily. A shortest perimeter bisector of a convex region will meet its two end edges at the same angle. This perimeter bisector need not be an area bisector too of the full region - indeed, assuming this shortest perimeter bisector to also be an area bisector of the full region, either piece resulting from this bisector can be altered to have an altered area without changing either its perimeter or the angle at which it meets the perimeter bisector; then, the perimeter bisector remains a shortest perimeter bisector but is no more an area bisector.

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"

Note (July 30th 2018): the fair partition problem, i understand has no problem in going hyperbolic. Indeed, the spicy chicken theorem statement (Karasev, Hubard and Aronov) holds for Hyperbolic space as well.



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' (http://nandacumar.blogspot.in/2016/06/non-congruent-tiling-ongoing-story.html): 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 https://arxiv.org/ftp/arxiv/papers/1307/1307.3472.pdf and one ended up at:

Conjectures:

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 (http://cs.smith.edu/~jorourke/TOPP/P78.html#Problem.78) 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:

https://mathoverflow.net/questions/285580/thinnest-covering-of-the-plane-by-regular-pentagons

https://mathoverflow.net/questions/256351/terrible-tilers-for-covering-the-plane/256493#256493



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(https://math.stackexchange.com/questions/1401327/packing-problem-of-semicircles-into-rectangle).

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.

Answers

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.