TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Thursday, September 29, 2022

On polygons inscribed in ellipses

Question: Given any ellipse, any number n and a point P on the ellipse. We need to find the max area inscribed polygon in the ellipse that has P as one of its vertices.

As P moves around the boundary the area of the max area inscribed n-gon will change. I have no guesses as to where it will be a minimum - by "where" I mean "P lies at which value of theta, the ellipse parameter".

The value of theta for which the n-gon is minimal could depend on two things - n and the eccentricity of the ellipse. If so how?

The same question can be asked with perimeter replacing area. And further possible tweaks include 2 vertices P and Q of the n-gon specified and so on.

Answer: When C is an ellipse, the area of the max area inscribed triangle remains constant as P moves around C - at each position of P, the max area inscribed triangle is one with centroid coincident with the center of C and has C as its Steiner circumellipse.

However, if instead of area, we consider perimeter, it is found that when C is an ellipse, the variation in the perimeter of the max perimeter inscribed triangle is within around 10% (experimental result) even when C is highly eccentric
(one thus has a very real geometric function that grows extremely slowly. The ratio between max and min among the set of the max perimeter inscribed triangles with one vertex fixed goes from 1 (circle) to just about 1.1 as the eccentricity of the ellipse - with say area constant - goes from 0 all the way to infinity),

Question: Among all planar convex regions of given area and perimeter, is the ellipse the shape that minimizes the variation in the perimeter of the max perimeter inscribed triangle with one vertex constrained to be at P - as P varies around the boundary of the convex region?

Wednesday, September 14, 2022

Optimal configs of planar convex bodies based on some integrals.

Recording a bunch of questions on convex geometry...

We consider relative positions of 2 given planar convex bodies C1 and C2 optimizing the 4 quanitities described below. In the following, by C1 or C2, we mean boundary of C1 or C2. And we are allowed to translate, rotate, flip both bodies (subcases are got by disallowing some of these transformations):

(1) minimize the integral over C1 of the distance of a variable point P on C1 to the closest point to it on C2.
(2) minimize the integral over C1 of distance of a variable point P on C1 to the farthest point to it on C2.
(3) and (4) minimize the two integrals above with C1 and C2 interchanged.

Questions:
- For any specified C1 and C2 will all the 4 different optimizations always give the same configuration (relative position) of C1 and C2 relative to each other? As examples given below show, all 4 optimizations need not give the same relative position of C1 and C2. Then, the natural question is: will all 4 optimizations give different configs in general? One can also ask for {C1, C2} pairs for which the optimal configs are most different (one needs to define difference suitably then).
--------
Note: It can be seen that the centers of mass of C1 and C2 (viewed as uniform laminae) need not be coincident in say, the optimal config that minimizes the integral over C1 of distance to closest point on C2. Indeed, let C1 be a square and C2, an identical square with a segment of a circle added - this circle segment is formed by a very high radius arc passing thru 2 adjacent vertices of the square; now, to minimize the integral, we should put the square portion of C2 directly over C1 (which is of course, just a square) and then, the CMs of C1 and C2 won't coincide.
--------
- Will any of these optimizations also automatically achieve other optimizations such as say, maximize the area (or perimeter) of the intersection between C1 and C2? Indeed, in example 2, two of the optimizations (3 and 4) need not achieve max area or perimeter of overlap.
- Will applying constraints on C1 and C2 (like say, they have same area, same perimeter, both, etc) cause some (or all) of the optimal configs to be the same? Or achieve say, max area of overlap?
- Finaly, what happens if we optimize based not only on the boundaries of C1 and C2 but the entire regions?

----------
Example 1: When C1 almost reduces to a point and C2 is say a finite square
Minimization (1) will put the small region anywhere on the boundary of square
and (2) will put small region at center of square.

Now, with C1 and C2 interchanged,
Minimization (3) will put small region at center of the square.
Minimization (4) too will have small region at center of square.
So, 3 of the optimizations coincide.
-------
Example 2: When C1 is a square of side 2 and C2 is a straight line of length 2*sqrt(2):
Minimization (1) - minimizing integral over square of nearest distance to line - will put the line segment as diagonal of square.
Minimization (2) - minimizing integral over square of farthest distance to line - will put line segment as diagonal of square
Minimization (3) - minimizing integral over line of nearest distance to square - will put line as perpendicular bisector of opposite sides of the square.
Minimization (4) - minimizing integral over line of farthest distance to square- will also put line as perpendicular bisector of opposite sides of square.
-------
Some earlier mathoverflow posts on similar matters:
- https://mathoverflow.net/questions/357124/on-comparing-planar-convex-regions-of-equal-perimeter-and-area
- https://mathoverflow.net/questions/417428/comparing-convex-planar-regions-of-equal-perimeter-and-area-2
- https://mathoverflow.net/questions/409981/on-ways-to-measure-the-difference-between-two-planar-convex-regions

------
Note: Instead of minimizing the integral over C1 of distance to farthest poiint on C2 (or with C1 and C2 interchanged), one can think of minimizing the max separation among all pairs of points (P1, P2) where P1 is from C1 and P2 is from C2. This optimization is symmetric between C1 and C2 so there are only 2 questions instead of 4 and in answers to both, one guesses that the centers of Mass of C1 and C2 are coindient.

Monday, September 05, 2022

Least Area Quadrilateral that contains a set of N planar points

Question: How does one find the least area quadrilateral (not necessarily convex) that contains a given set of N points in general position on the plane?

The least area containing quadrilateral (non-convex) could be degenerate in some cases - the union of a triangle and an infinitely thin 'sliver'. By general position, we mean no three points are collinear. And if there are more than 4 points in total, the quad, even if it has a degenerate portion, will not be of zero area.

Can one say that a least area quadrilateral (such a quadrilateral may not be unique) will have at least one edge flush with an edge of the convex hull of the set of n points? Or maybe one can ask, if *every* least area quad containing the points has an edge flush with an edge of the convex hull. I really don't know.

Note: The question has a natural generalization to finding least area m-gons that contain N points on the plane.
-----------
The above question is copied from a Mathoverflow post.