I have a straight line which intersects a convex polygon in 2D plane. There exists a circle with constant radius. The center of circle is moving on this line. So at first the polygon and circle don't intersect with each other, as the circle gets closer to the polygon the intersection increases and then decreases as they go further from each other. I want to prove the area of the intersection of the convex polygon and circle doesn't have local minima (as the circle moves on the line).

  • $\begingroup$ It must have local mimina. It is zero far away, and always non negative, hence 'most' points are local minima. $\endgroup$ – copper.hat Jun 8 '15 at 18:58
  • $\begingroup$ @copper.hat I think that the OP means that the area function is unimodal (i.e., monotonically increasing and then monotonically decreasing). $\endgroup$ – Michael Burr Jun 8 '15 at 19:41
  • $\begingroup$ @copper Actually I meant there is not a case in which the area first decreases then increases. So if you have your circle at point (t,0) (with out loss of generality assume the line is on x axis) then it's not possible to have intersection area less than when circle is at (t+epsilon,0) and (t-epsilon,0) $\endgroup$ – ladan Jun 8 '15 at 19:52

Yes, the area functional is unimodal and doesn't have any "true" local minimum.

WOLOG, we will assume the circle has unit radius and at time $t$, its center is located at $(t,0)$.
Let $C_t$ be the region covered by the circle at time $t$ and $K$ be the convex polygon.

Let $S_t = C_t \cap K$ and $\mu(S_t)$ be its area. If the area functional $\mu(S_t)$ has a "true" local minimum at $t = t_0$, we can find two $t_1 < t_0 < t_2$ such that $\mu(S_{t_1}), \mu(S_{t_2}) \ge \mu(S_{t_0})$ and at least one of these two inequalities is strict. Choose a $\lambda \in (0,1)$ such that $t_0 = \lambda t_1 + (1-\lambda) t_2$. We claim that

$$S_{t_0} \supset \lambda S_{t_1} + (1-\lambda)S_{t_2} = \big\{\; \lambda p_1 + (1-\lambda)p_2 : p_1 \in S_{t_1}, p_2 \in S_{t_2}\;\big\}\tag{*1}$$ It is clear all these $S_{t_i}$ are convex and by Brunn-Minkowski inequality, we have $$ \sqrt{\mu(S_{t_0})} \ge \sqrt{\mu(\lambda S_{t_1} + (1-\lambda) S_{t_2})} \ge \lambda\sqrt{\mu(S_{t_1})} + (1-\lambda)\sqrt{\mu(S_{t_2})}\\ \stackrel{*}{\ge} \lambda\sqrt{\mu(S_{t_0})} + (1-\lambda)\sqrt{\mu(S_{t_0})} = \sqrt{\mu(S_{t_0})} $$ Since at least one of $\mu(S_{t_1})$, $\mu(S_{t_2})$ is greater than $\mu(S_{t_0})$, the inequality marked by a "*" above is actually strict. This leads to the contradiction that $\sqrt{\mu(S_{t_0})} > \sqrt{\mu(S_{t_0})}$. As a result, we find $\mu(S_t)$ doesn't have any "true" local minimum.

What remain to do is justify the claim $(*1)$. The easiest way to see it is lifting everything to $\mathbb{R}^3$. Let

$$\tilde{K} = K \times \mathbb{R},\quad \tilde{C} = \{ (x,y,z) \in \mathbb{R}^3 : ( x - z )^2 + y^2 \le 1 \} \quad\text{ and }\quad \tilde{S} = \tilde{K} \cap \tilde{C} $$ Let $P_\alpha$ be the plane with constant $z = \alpha$. It is easy to see $\tilde{C}$ and $\tilde{K}$ are convex regions in $\mathbb{R}^3$, this means $\tilde{S}$ is also convex. Furthermore, for any $\alpha$, we have

$$\tilde{S} \cap P_\alpha = S_\alpha \times \{\alpha\}$$

Consider the convex hull of $\tilde{S} \cap ( P_{t_1} \cup P_{t_2} )$ in $\tilde{S}$. Since $\tilde{S}$ is convex, it contains this convex hull. In particular, $\tilde{S}$ contains the set $$X = \lambda ( \tilde{S} \cap P_{t_1} ) + (1-\lambda) ( \tilde{S} \cap P_{t_2} )$$ For any $p \in X$, rewrite it as $\lambda p_1 + (1-\lambda) p_2$ with $p_i \in \tilde{S} \cap P_{t_i}$. Since the $z$-coordinate of $p_i$ is $t_i$, the $z$-coordinate of $p$ is $\lambda t_1 + (1-\lambda) t_2 = t_0$. i.e. $$X \subset P_{t_0}\quad\implies\quad X \subset \tilde{S} \cap P_{t_0} = S_{t_0} \times \{t_0\}$$ It is not hard to see $$X = (\lambda S_{t_1} + (1-\lambda) S_{t_2} ) \times \{t_0\}$$ This implies $\lambda S_{t_1} + (1-\lambda) S_{t_2} \subset S_{t_0}$ and claim ($*1$) is justified.

  • $\begingroup$ [+1] Once more, I am amazed at your exceptional answers in geometry, served by an excellent redaction. $\endgroup$ – Jean Marie Jan 8 '18 at 8:22

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.