5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Is a convex "lamina" the same as a convex polygon? $\endgroup$ Aug 19, 2021 at 23:32
  • $\begingroup$ Switched from 'lamina' to 'region'. Thank you. $\endgroup$ Aug 20, 2021 at 1:38
  • 3
    $\begingroup$ I think a similar maximum intersection problem for subsets of the cyclic group under translations would be reducible to your problem (e.g. take the convex hull of the unit disk with $\{((1+h)\cos 2 \pi i/N, (1+h)\sin 2 \pi i/N): i \in A\}$ with very small h for each subset A). Then I think the greedy method fails e.g. for {1, 3, 20, 40, 60}, {2, 4, 20, 40, 60} and {1, 2, 3, 4}. $\endgroup$ Aug 20, 2021 at 3:53
  • $\begingroup$ The reduction in my comment above should also work with minor modifications for the problem in your "further question" about minimum union. $\endgroup$ Aug 20, 2021 at 21:11
  • $\begingroup$ Thanks! The example you give appears to apply to the case where the rigid motions allowed for the planar regions include rotations. Not sure if a counter can be found if only translations are allowed. $\endgroup$ Aug 21, 2021 at 6:38

2 Answers 2

5
$\begingroup$

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)$$

enter image description here

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)$.

enter image description here

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.

$\endgroup$
3
  • $\begingroup$ Nice example. This uses reflections. Perhaps counter examples to the 'simple method' can still be found even if only translations are allowed among rigid motions,.. $\endgroup$ Aug 21, 2021 at 6:36
  • 1
    $\begingroup$ If only translations are allowed, let $A$ be the triangle on $(0,0), (1,0), (0,1)$, let $B$ be the triangle on $(\frac14,0), (\frac14,1),(-\frac34,1)$, and let $C$ be their intersection. Then for maximizing $|A\cap B\cap C|$ we should leave everything in place, but $|A\cap B|<|A\cap B’|$, where $B’$ is the result of moving $B$ to the right by $\frac34$ . So regardless of whether the allowed motions are just translations, or translations and rotations, or translations and rotations and reflections, the simple method will not work. $\endgroup$
    – Matt F.
    Aug 22, 2021 at 13:59
  • $\begingroup$ In my previous comment, the last ordered pair should have been $(-\frac34,0)$ $\endgroup$
    – Matt F.
    Aug 23, 2021 at 13:06
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Thanks! It is really amazing that so far no exact polynomial time algorithm has been found to compute maximal intersection between two polygonal regions. I guess the analogous question about the union of convex regions might be an easier problem. Added a bit to the question above on that. $\endgroup$ Aug 20, 2021 at 15:03
  • $\begingroup$ @NandakumarR: Although I could not find an exact algorithm in the literature, it is difficult to be certain that no exact algorithm is known. In any case, it is a difficult problem. $\endgroup$ Aug 20, 2021 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.