Does this operation result in a convex set?

56 Views Asked by At

Denote by $cm(B)$ the center of mass of the set $B\subseteq\mathbb{R}^2$. Given two convex sets $A,X\in \mathbb{R}^2$, define $Y$ in such a way that $X\cap A\neq \emptyset$ if and only if $cm(A)\in Y$.

Is $Y$ convex? Can we generalize the result to arbitrary $\mathbb{R}^d$? Is there any relatioinship with Minkowski sum.

The question above is adapted from the notes of Discrete and Polyhedral Geometry by Igor Pak, in which $Y$ is confirmed to be convex. But I can not find a proof.

2

There are 2 best solutions below

6
On

Suppose $A_1$ and $A_2$ are both convex and intersect $X$; then $a_1$ and $a_2$ are both in $Y$, and we need to show that $(1-t)a_1 + t a_2$ is in $Y$ for $t \in [0, 1]$.

Well, take a radius $r$ so large that the disk of radius $r$ about either point meets $X$, i.e. $$ D(a_{i}, r) \cap X \ne \emptyset ~for ~~i = 1, 2. $$

Now the disk $D( (1-t)a_1 + t a_2, r)$ has center of mass $(1-t)a_1 + ta_2$, which is a point of $X$ (because $X$ is convex). This disk is a convex set that intersects $X$, and its center of mass is the desired point, so that COM is in $Y$.

0
On

$\DeclareMathOperator{\cm}{cm}$ $\newcommand{\R}{\mathbb{R}}$ The original question doesn't really make sense, since $A\subseteq\R^2$ is a fixed set, so $Y$ is either empty or a single point, both of which are trivially convex. However, the question that I believe Robin was trying to ask is what actually comes out of Pak's book, proof of Corollary 1.6. The revised question is as follows:

Let $X,A\subseteq\R^2$ be convex sets (we also need to assume $A$ is bounded). Define a set $Y\subseteq\R^2$ as follows $$Y=\left\{\cm(A')~|~A'\text{ is a translate of }A\text{ such that }X\cap A'\neq\varnothing\right\}$$ How can we show that $Y$ is convex?

Answer: Let $a_0,a_1\in Y$, and let $A_0,A_1$ be the translates of $A$ with centres of mass $a_0,a_1$ respectively. Let $x_0\in X\cap A_0$ and let $y_1\in X\cap A_1$. Denote by $x_1$ the translate of $x_0$ in $A_1$ and by $y_0$ the translate of $y_1$ in $A_0$. Now for $t\in[0,1]$ let $a_t=ta_1+(1-t)a_0$, and similarly define $x_t$ and $y_t$; and let $A_t$ be the translate of $A$ with centre of mass $a_t$. Firstly, note that $Q=(x_0x_1y_1y_0)$ is a quadrilateral (perhaps degenerate, i.e. a segment); and that the segment $[x_0,y_1]$ is a diagonal of $Q$. But also the segment $[x_t,y_t]$ joins two opposite sides of $Q$. Therefore $[x_0,y_1]\cap[x_t,y_t]\neq\varnothing$, for all $t\in[0,1]$. By convexity of $X$, the segment $[x_0,y_1]$ is contained in $X$, and by convexity of $A_t$, the segment $[x_t,y_t]$ is contained in $A_t$. Thus $\varnothing\neq[x_0,y_1]\cap[x_t,y_t]\subseteq X\cap A_t$, and so $a_t\in Y$, for all $t\in[0,1]$.