TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Friday, November 22, 2019

Convex Containers of Rectangles

This post continues this earlier post: https://nandacumar.blogspot.com/2019/11/convex-containers-of-triangles.html

We considered this variant of the question mentioned therein:

"Given a rectangle R, find the convex region C of maximum area (perimeter) containing R such that R is the maximum area (perimeter) rectangle contained in C."

We tried this experiment: Take  rectangle R and numerically find the smallest area ellipse E containing it. Then, it is seen that for E, the largest area inscribed rectangle is the same R. This property holds for any R. So, one guesses that the answer to the area case of above question is an ellipse.

  However, with perimeter, things are different. If E is the least perimeter ellipse containing a given R, then, the max perimeter rectangle contained within E is not R itself - unless R is a square. This indicates that the answer C for the perimeter version of the question may not be an ellipse.

Experiment: Given a rectangle R as input, we repeated the following steps several times:

{
1. find the smallest perimeter ellipse E that contains R (we use a series to calculate perimeter of E).
2. find the largest perimeter rectangle contained within E. This rectangle (R') is different from R. Replace R with R'
}

Finding: The E calculated in the first iteration obviously has a much larger perimeter than input R. However, within a few dozen iterations, E and R both grow flat (the minor axis and width tend to zero) and their perimeters both tend to a value roughly midway between the perimeters of the initial R and E. This happens whenever initial R is not a square; even a if initial R had a 1 in 1000 difference between length and width, this convergence happens within around 60 iterations.

Wednesday, November 20, 2019

Convex Regions and 'Kissing Numbers'

This post continues a thread from this post: https://nandacumar.blogspot.com/2019/01/a-bit-more-on-kissing-numbers.html

Given a 2D convex region C, let us define its kissing number K_0 to be the largest possible number of copies of C that can be arranged around a central copy of C (call this C_0) and touching C_0.

Question: Given values A and P, which is the convex region C with area = A and perimeter = P and with **least** K_0? Is it always an ellipse?

Note: One can also define 'K_1' to be *the largest number of copies of C that can be arranged around a central C_0 such that the copies touch either C_0 or a copy that touches C_0*. So one can ask the shape of C with specified A and P and with least K_1. And these questions have natural higher dimensional analogs.

Further question: Given any C, we need to find its K_1. IOW, we need to find an arrangement of copies of C around a central C_0 such that they all touch either C_0 or a copy that touches C_0. Now, is it sufficient to first arrange K_0 copies all kissing C_0 and then to arrange maximum number of copies all touching at least one of these K_0 copies? Are there C's where such a 'greedy' approach fails?

Sunday, November 10, 2019

Convex Containers of Triangles

This post is also in continuation of this document written in early 2018:
https://arxiv.org/abs/1802.10447

Given an arbitrary triangle T.

1. How does one find the convex shape C_M of largest area containing T such that T is also the largest area triangle that is contained within C_M?

Guess: for any T, C_M might be some ellipse. However, for a given T, if E is the smallest area ellipse that contains T, T is probably not necessarily the largest triangle that E can contain.
Note: Above question can also be asked with perimeter replacing area.

2. What about the convex shape C_m of smallest area (perimeter) contained within T such that T is also the smallest area (perimeter) triangle that contains C_m?

Guess: again an ellipse.

As usual, one can wonder about 3D. The question might have some connection with Hilbert and Cohn Vossen's statement that any stone will reduce to an ellipsoid on exposure to erosion.
--------
This question has been asked online: https://mathoverflow.net/questions/345681/on-convex-regions-containing-and-contained-within-a-given-triangle . Further illuminations awaited....
--------

Friday, November 08, 2019

Isoceles Triangles - Further Questions

Continuing from this earlier post: https://nandacumar.blogspot.com/2019/10/on-isoceles-triangle-question.html, let me record the following questions:

- Given any 2D convex region C with a mirror symmetry. We need to find the smallest area (likewise smallest perimeter) triangle that contains C. Is it sufficient to only search among isosceles triangles aligned along the direction of mirror symmetry of C for answers to both questions?

- Similarly, if we seek the largest area (largest perimeter) triangle contained within C, is it enough to look only among isosceles triangles aligned along the direction of symmetry of C?

Updates should follow...

Update: Both questions have been answered in the negative by nice and simple counterexamples here: https://mathoverflow.net/questions/345552/smallest-triangles-that-contain-2d-convex-regions-with-reflection-symmetry
Thanks!

Sunday, November 03, 2019

On 'Bi-Convex' Tiles

Let us define a 'biconvex polygonal region' as a non-convex polygonal region that can be cut into 2 convex regions. The more interesting biconvex regions are those which can be cut into 2 convex regions, which are necessarily noncongruent. Let us call them asymmetric biconvex regions.

Question: To find how good bi-convex polygons, especially asymmetric ones, are for tiling.

Here is a bi-convex pentagon that tiles the plane. It is easily seen that infinitely many such pentagons (even asymmetric ones) can be constructed.



A biconvex Hexagonal tile. Again, it is easily seen that there are infinitely many such hexagons (indeed, asymmetric ones)



A biconvex heptagon. Infinitely many such heptagons can easily be found (including asymmetric ones)



Two biconvex octagonal tiles, both asymmetric. By attaching the unit square at various positions on the long rectangle, one can make infinitely many biconvex asymmetric octagonal tiles.



Right now, I don't have any biconvex 9-gons that can tile the plane.
Take any hexagon that can tile the plane in the usual lattice. By fusing two copies of any such hexagon along an edge, we can trivially construct infinitely many biconvex 10-gons that tile the plane. However, here is an asymmetric biconvex 10-gon that tiles - it can be cut into a heptagon and a pentagon.



Questions: Are there (infinitely many) biconvex 9-gons that tile the plane? There may only be a few asymmetric biconvex 10-gons that that can tile. Which are they? And are there any biconvex 11-gons or 12-gons that can tile the plane? With higher number of tiles, the answer must be negative.