On intersections of several convex regions

Question

Question: Given n convex planar regions. Required to place them (in suitable position and orientation) so that that part of the plane lying under all the regions (their common intersection) is of maximum area.

If we first place any two of the planar regions such that their intersection is maximized, then, place a third region so that its max intersection with the max intersection of the first two is maximized and so on, are we guaranteed to find the maximum common intersection of all n regions - irrespective of the order in which we consider them? I have no counterexample to this simple method.

Note: I don't know if the algorithmic problem of placing two convex polygonal regions so that the area under both is maximized has been optimally solved. The above question can also be asked replacing area with (say) perimeter.

Further Question: One can ask a similar question with the union of planar convex regions - how to 'stack' n regions one above the other so that the convex hull of their union has least area / perimeter. Guess: One could begin by placing the region with maximum width above the region with maximum diameter such that the width or the former is perpendicular to diameter of the latter.

Answer 1

The simple method will not always work.

Consider the trapezoids $$A: (1,0), (2,1), (-2,1), (0,0)$$ $$B: (1,0), (2,1), (0,1), (-2,0)$$ and their pentagonal intersection $$C: (1,0), (2,1), (0,1), (-1,\frac12), (0,0)$$

Clearly the maximal overlap of shapes $A$, $B$ and $C$ is in these positions and orientations; no rotation, translation, or reflection can get an overlap with area greater than $C$.

But if we had looked first for the maximal overlap of $A$ and $B$, we would have found $|A\cap B|<|A\cap B’|$, where $B’$ is a version of $B$ reflected about the line $y=\frac12$: $$B’: (2,0), (1,1), (-2,1), (0,0)$$

As a result, the simple method will not get the maximal area for these $A$, $B$, $C$. The same argument shows that the simple method will not get the maximal perimeter either.

Update, without needing reflections

Suppose that in polar coordinates:

$A$ is the convex hull of the unit circle together with $(\sec\frac\pi8,0),(\sec\frac\pi9,\frac\pi2),(\sec\frac\pi9,\pi)$.

$B$ is the convex hull of the unit circle together with $(\sec\frac\pi8,0),(\sec\frac\pi9,\frac{3\pi}{4}),(\sec\frac\pi9,\frac{5\pi}{4})$.

$C$ is the convex hull of the unit circle together with $(\sec\frac\pi8,0)$.

Each point at radius $\sec(\theta)$ increases the area by $f(\theta)=\tan(\theta)-\theta$, and covers $2\theta$ of the circumference. We calculate that $2f(\pi/9)>f(\pi/8)$.

So again, the maximal overlap of shapes $A$, $B$ and $C$ is in these positions and orientations; no rotation, translation, or reflection can get an overlap with area greater than $C$.

But if we had looked first for the maximal overlap of $A$ and $B$, we would have found $|A\cap B|<|A\cap B'|$, where $B'$ is a rotation of $B$ by $\pi/4$.

As a result, the simple method will not get the maximal area for these $A$, $B$, $C$. The same argument shows that the simple method will not get the maximal perimeter either.

Answer 2

Addressing the OP's "Note," as far as I know, this is the algorithm status: There are fast approximation algorithms, but I have not found an exact algorithm (except when only translations are permitted).

Ahn, Hee-Kap, Otfried Cheong, Chong-Dae Park, Chan-Su Shin, and Antoine Vigneron. "Maximizing the overlap of two planar convex sets under rigid motions." Computational Geometry 37, no. 1 (2007): 3-15. DOI.

"for any $\varepsilon$, we compute a rigid motion such that the area of overlap is at least $1-\varepsilon$ times the maximum possible overlap."

This was improved to a PTAS to maximize the volume of two polytopes in $\mathbb{R}^d$ in dimension $d$:

Vigneron, Antoine. "Geometric optimization and sums of algebraic functions." In Proceedings 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 906-917. SIAM, 2010. DOI