Tiling With Similar Tiles

Question 1: Is there a polygon P - convex or otherwise - that
1. cannot tile the plane
and
2. tiles the plane when copies of P and some other polygon(s) all similar in shape to P but of different size(s) can be used?

Basically, with copies of P alone we should be able to form a layout with gaps which are all similar in shape to P and of different size(s).

Motivation: In basic tiling, we are constrained to use congruent copies of a candidate polygonal region (congruent up to some isometry) to fill the plane without gaps. Here, we consider relaxing the constraint to allow scaled copies of the candidate region and try to see whether this relaxation can non-trivially improve the chance a candidate region has of being a tile.

Question 2: Is there a P such that it is not a rep-tile but a large copy of P can be tiled by several units all similar to P?

Note: By rep-tile, we mean a polygon that can be cut into some finite number of equally scaled down copies of itself. So, the P one is looking for cannot be tiled by any finite number of equally scaled down copies of itself but can be tiled with copies of itself which have been scaled down by factors that are different among themselves.

Note added on July 21st, 2020: The question has been mostly answered by the responses at https://mathoverflow.net/questions/365451/tiling-with-similar-tiles, mostly in the affirmative, by examples. So, one could ask if polygons satisfying above-specified requirements have common necessary properties, whether such polygons are finitely many and so on...

Largest Semidisk inside a Convex Polygon

The preprint https://arxiv.org/abs/2005.10245 had addressed the question of finding the smallest semicircular region (semidisk) that contains a given set of points - basically that contains the convex hull of the set of points. Here, we ponder another question: find the largest semicircle inscribed in a convex polygon.

Here is an attempt to sketch an algorithm for an N vertex convex P.

Observation: The largest semicircle inside a convex polygon P necessarily has both end points of its diameter on the boundary of P.

We need to consider two classes of semicircles as candidates.
(1) Semicircles with both end points on different edges of P
(2) Semicircles with both end points on the same edge of P:

Note: Here, we discuss only case 1. Case 2 can be done with slight modifications to what we show.

For each pair of edges {E1, E2} of P (let their lengths d1 and d2), we do the following:
============================
Every chord of P from somewhere on E1 and ending somewhere on E2 is a candidate for the diameter for the largest inscribed semicircle – obviously, the midpoint of this chord has to be center and half the length of the chord, the radius of a candidate semicircle. Let us parametrize the edges E1 and E2 with α and β - distances measured along them from one end point to the other. To every (α, β) pair corresponds a candidate diameter chord of P and 2 semicircles with this as diameter – the two lie on either side of the candidate diameter. For each point (α, β) that lies in a rectangle on the α- β plane, we can easily find the value of corresponding semicircle radius as a continuous function of α and β. First we plot these radii as a curved surface above (α, β) as R(α, β).

Now, we calculate how these semicircles for edge pair {E1, E2} are interfered with by edges (O(N)in number) of P - including E1 and E2. Here is how we process one such edge E:

For each α and β, apart from R(α, β), we also have the semicircle center whose coordinates are also functions of α and β. So, for a given edge E, we can find minimum distance from E to this center(α, β) as a continuous function of α and β; call this d(E, α, β) and it forms another surface above the α-β plane.

Evidently, at any point above (α, β), if d(E, α, β) < R(α, β), that (α, β) chord of the polygon is disallowed by edge E – in other words, viewed upwards from the (α, β) plane, at least a portion of the R(α, β) surface has now become ‘screened’ by the d(E, α, β) surface.

So, for every edge E of P including E1 and E2, we plot d(E, α, β) above (α, β), and from the portion of the plot of R(α, β) that is still ‘visible’ from the (α, β) plane (ie. left unscreened by all the d surfaces), pick the highest point and this gives, for the edge pair {E1, E2}, the highest radius semicircle that can be drawn with diameter end points on E1 and E2.
============================
The above processing for each edge pair {E1, E2} appears to be O(N^2) in complexity – we need to compute intersections of O(N) d surfaces sequentially with the R-surface and with each intersection, the complexity of the remaining part of the R- surface could increase to O(N).

So, since there are O(N^2) pairs of edges, we roughly estimate the overall complexity of the algorithm as O(N^4).

Of course, there are some ‘filters’ which eliminate a lot of the processing. For example:

For each candidate diameter, at its end points the edges E1 and E2 necessarily either (1) converge to one side of the candidate edge and diverge towards the other side (2) are parallel. On the side towards which E1 and E2 converge, no semicircle is possible; they are all ruled out. See the picture below:

For any chord joining the given E1 and E2, only the candidate semicircle and other edges of P on the left side of the chord need to be considered because E1 and E2 together converge towards the right.

However, this filter does not seem to reduce the complexity from O(N^4).

Further Questions (10th December 2020): Just as the semidisk, one can ask for  algorithms to find the largest circular segment (two cases, the segment with most area and the one with most perimeter) and largest sector (again, area and perimeter cases) that can be inscribed in a given convex (and further, general) polygon.

Covering with Rectangles etc - 2

Here, we add a bit to this earlier post:
https://nandacumar.blogspot.com/2019/07/covering-with-rectangles.html

Basic question: To cover a given convex shape C with N rectangles (no further constraints on the dimensions of the rectangles; they could be different) such that the sum of the areas of the N rectangles is the least.

Variant: To cover C with N instances of the same shape - the sizes of the 'covering units' could be different; they just need to be similar to each other - such that the covering units have the least area sum. Eg: covering C with squares, equilateral triangles or triangles all similar to one another.

Guess: In both above questions, the best layout is always such that the N covering units have no overlaps among themselves. If C could be non-convex, they may overlap.

Remarks on this Guess: When the covering units are all circles or mutually similar instances of a convex polygonal shape with large number of sides - then, the units necessarily overlap so the above guess does not hold for those shapes. But it seems plausible when the covering is done with a set of N mutually similar triangles or with N rectangles (which need not be similar among themselves)

However, here is a Partial Counter-example:
Consider C to be as shown in picture in red (its angles are 90, 120, 90 and 60 degrees). Take N=3 and the covering shape to be 'equilateral triangle'. It seems the cover of C with 3 equilateral triangles of least total area of units necessarily has an overlap - two such arrangements are shown in pic and that any covering layout with 3 non-overlapping equilateral triangles will have greater combined area of covering units..


So, the guess might have to be restricted only to covering with rectangles. And as usual, onecasks, what about 3D?
Note 1: In the post linked at the top, we observed that if the problem is that of filling the interior of C with N rectangles none of which has any point outside C, then, the coverage of the interior can be improved by allowing the units to overlap - although at the cost of an increased sum of the areas of units.

Note 2: Naturally, questions on finding algos which (1) cover C optimally with N suitable rectangles and (2) fill as much of the interior of C with N suitable rectangles could be asked. One feels algorithms of class (1) are easier to find.