3
$\begingroup$

Let $P$ and $Q$ be two convex polygons in $\mathbb{R}^2$. Given $a > 0$, denote by $aP$ its image under the dilation by $a$ centered around the origin (i.e. the polygon obtained by replacing each vertex $(p_0,p_1)$ by the vertex $(ap_0, ap_1)$). Let $C(P,Q)$ denote the convex hull of the union $P \cup Q$, and let $N(P,Q)$ denote the number of new edges created (i.e. edges in $C(P, Q)$ which do not appear in $P$ or $Q$). Let $P+Q$ denote the Minkowski sum of the two polygons.

Let a Gaussian random polygon $P$ be the convex hull of $n$ random, independent points in $\mathbb{R}^2$ sampled according to the standard normal distribution, for some $n$; here $n$ is the ``size" of the polygon. (Also if $X$ is a Gaussian centered at $0$ with variance $1$, then $|X|$ follows the half-normal distribution).

Question: Let $P$ and $Q$ are Gaussian random polygon of fixed size, and let $a,b$ be drawn from the half-normal distribution. Show the following holds (here the expectation is over the distributions from which $P, Q$ are drawn, and the variables $a,b$): $$ \mathbb{E}(N(aP, bQ))<10$$

Above $10$ is an arbitrarily chosen constant, the key point is that it does not depend on the number of vertices in the polygons $P$ and $Q$. Ideally the proof should show that the above inequality holds when $P, Q$ are fixed and "sufficiently generic" (this stronger claim does not always hold for arbitrary choices of $P$ and $Q$; the above question is precise and avoids the inherent ambiguity of this statement). The next question is a more general version, with Minkowski sums.

Question 2: Let $a_1, \cdots, a_m, b_1, \cdots, b_n$ be chosen from a half-normal distribution, and $P_1, \cdots, P_m, Q_1, \cdots, Q_n$ be Gaussian random polygons of fixed sizes. Prove the following statement: $$ \mathbb{E}(N(a_1P_1+\cdots+a_mP_m, b_1Q_1+\cdots+b_nQ_n)) < 10$$

One special case I'm particularly interested in is when the sizes of the Gaussian polygons is 2 (i.e. they are line segments).

Unfortunately it turns out that the inequality from Question 1 does not always hold if the polygons $P$ and $Q$ are fixed (hence the need for the Gaussian random distributions); a counterexample can be constructed as follows. Suppose $O P_1 P_2 \cdots P_n$ is a convex polygon, with the vertices in clockwise order. Let $P_i P_{i+2}$ intersect $O P_{i+1}$ at the point $Q_{i+1}$. The points should be chosen carefully so that the ratio $\frac{OQ_{i+1}}{OP_{i+1}} < \epsilon$, where $\epsilon>0$ is small (this can be done inductively). Let $P$ be the polygon $OP_2 P_4 ...$ and $Q$ the polygon $OP_1 P_3 ...$. With this choice, it is easy to see that $\mathbb{E}(N(aP, bQ))$ grows linearly with $n$.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.