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.

0 Comments:

Post a Comment

<< Home