TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Wednesday, September 18, 2019

Largest Regular Polygons that Fit into a Polygon

It is well known that for any 2D region P (not necessarily convex), the center of the largest circle that can be drawn in P necessarily lies on the medial axis of P - the medial axis of P is the set of all points in its interior with more than one closest point on the boundary of P.

Question 1: What if we are looking for the largest equilateral triangle or largest square or in general the largest regular N-gon that can be drawn inside P/

Observation: The center of the largest N-gon need not lie on the medial axis of P. Here is an example.



The figure shows a circle and its largest contained square (the latter shown with broken boundary). The slightly larger red square touches the circle at two points and two of its corners poke out of the circle. The centers of the two squares are also marked. Now consider P to be the union of the circular region and the big square. Obviously, the largest square that can be drawn inside P is the red square. Its center has only one closest point on the boundary of P (the other end of the blue broken line) and so is not on the medial axis of P.

Note: Even if P is restricted to be convex, the center of the largest square inside it need not be on the medial axis. Indeed, take a square and inflate three of its sides very slightly outwards, keeping the boundary convex with all vertices fixed and leaving the 4th side untouched. If this object is taken as P, its largest contained square is the one we started with. The center of this square has only a single closest point on the boundary of P - the mid point of the untouched 4th side of the original square.

The question of the largest contained regular N-gon should be a well studied area. I shall link references as I find them.
------------
This is more speculative...
Question 2: Given a convex region C and a positive integer n>=3. Let A(n) be the area of the largest n-gon that can be drawn inside C. What could one say in general about the behavior of A(n) as n varies?

For example, if C is an equilateral triangle, A(n) appears to steadily decrease with n from the area of C itself for n =3 until the incircle is reached for n = infinity. If C is a circle, A(n) appears to steadily increase from the inscribed equilateral triangle (n =3) to C itself for infinite n. So, do we have something like: "For any C, there is a unique n for which A(n) is a maximum and it is monotonically increases or decreases on either side of that n"?
Or one can wonder: Can one construct a convex C - or even a non-convex region - such that the derivative of A(n) changes sign arbitrarily many times?
-----------
Question 3: Given a general convex region C, to find the largest regular polygon that is totally contained in it. Basically, one needs to find that particular value of n for which a regular n-gon contained in C has the largest area.
A specific case: Given a specific value of n, can one find some triangle such that the largest regular polygon inscribed in the triangle has exactly n sides? One guess is that n cannot be arbitrarily large if C is restricted to be some triangle. iow, the largest contained regular n-gon cannot be the incircle for any triangle.

Remark: This set of questions suggests a way to classify all convex regions - not only polygonal ones - into a countable number of sets given by the value of n such that the regular n-gon inscribed in a polygon is maximum.

0 Comments:

Post a Comment

<< Home