37
$\begingroup$

Let's call a polygon $P$ shrinkable if any down-scaled (dilated) version of $P$ can be translated into $P$. For example, the following triangle is shrinkable (the original polygon is green, the dilated polygon is blue):

enter image description here

But the following U-shape is not shrinkable (the blue polygon cannot be translated into the green one):

enter image description here

Formally, a compact $\ P\subseteq \mathbb R^n\ $ is called shrinkable iff:

$$\forall_{\mu\in [0;1)}\ \exists_{q\in \mathbb R^n}\quad \mu\!\cdot\! P\, +\, q\ \subseteq\ P$$

What is the largest group of shrinkable polygons?

Currently I have the following sufficient condition: if $P$ is star-shaped then it is shrinkable.

Proof: By definition of a star-shaped polygon, there exists a point $A\in P$ such that for every $B\in P$, the segment $AB$ is entirely contained in $P$. Now, for all $\mu\in [0;1)$, let $\ q := (1-\mu)\cdot A$. This effectively translates the dilated $P'$ such that $A'$ coincides with $A$. Now every point $B'\in P'$ is on a segment between $A$ and $B$, and hence contained in $P$.

enter image description here

My questions are:

A. Is the condition of being star-shaped also necessary for shrinkability?

B. Alternatively, what other condition on $P$ is necessary?

$\endgroup$
7
  • $\begingroup$ What do you mean by translate? The U shape can certainly be shrunk into itself by making it tiny in a corner, but it has to cross its own boundaries to do so. $\endgroup$
    – djechlin
    Oct 2, 2014 at 8:02
  • $\begingroup$ By "translate" I mean just move. I.e., you are given a down-scaled version of the polygon, and you are only allowed to move it around, but you are not allowed to shrink it further. $\endgroup$ Oct 2, 2014 at 8:05
  • 1
    $\begingroup$ Do you have an example of a polygon which is not star-shaped, but is still shrinkable? Furthermore, it might be interested to consider "continuous shrinkable" defined as follow: Mark any point in the polytope. As the size decreases, we can "move" the shrinked polygon s.t. the marked point follows a continuous path. Your star-polytopes have this property (choosing A to be the marked point). Question is, are there shrinkable polytopes which are not continouous shrinkable? $\endgroup$ Oct 2, 2014 at 8:16
  • 2
    $\begingroup$ @PerAlexandersson I don't have such an example. I believe that being star-shaped is necessary, but I don't have a proof. $\endgroup$ Oct 2, 2014 at 8:20
  • 1
    $\begingroup$ Tangentially related: "Shrink polygon to a specific area by offsetting." $\endgroup$ Oct 2, 2014 at 12:03

4 Answers 4

27
$\begingroup$

Any simply connected polygon must be star-shaped to be shrinkable. I have made minor edits below to treat the more general case.

Let $D$ be a polygon with convex hull $H$. Assume we are given a non-trivial shrinking of $D$; view this as a map from $H$ to itself. This map must have a fixed point $x$, either by algebraic topology or an iterative construction.

This means it suffices to consider only dilations centered at a point $x$ in $H$, rather than dilations followed by translations.

For any $x$, if there is a point $y$ in $D$ so that the segment from $x$ to $y$ is not contained in $D$, then a $(1-\epsilon)$-dilation of $H$ centered at $x$ will not carry $D$ into $D$ for any positive $\epsilon$ smaller than some $\epsilon(x)>0$. If $D$ is not star-shaped, take the minimum $\delta$ of $\epsilon(x)$ over $x\in H$, and then no $(1-\delta)$-dilation of $H$ centered at a point in $H$ carries $D$ into $D$.

$\endgroup$
14
  • $\begingroup$ Why do you need to assume that the original polygon is simply-connected? $\endgroup$ Oct 2, 2014 at 8:55
  • $\begingroup$ I was using it for the algebro-topological proof that there is a fixed point. I think the iterative construction (replace $D$ with the image of the shrink map) should work to give a fixed point in the general case. $\endgroup$ Oct 2, 2014 at 9:01
  • 1
    $\begingroup$ Thanks. It is gladdening to have a necessary condition that matches the sufficient condition. $\endgroup$ Oct 2, 2014 at 16:37
  • 2
    $\begingroup$ I do not follow; why does the existence of a fixed point imply that we need to consider only the dilations centered at $x$? (It is clear in the proof of Włodzimierz Holsztyński, but not in this proof. Is there a transparent way of seeing it?) $\endgroup$
    – Boris Bukh
    Oct 7, 2014 at 14:33
  • 2
    $\begingroup$ @GabrielC.Drummond-Cole, that does not address my question. You start with a single non-trivial shrinking, and consider its powers, get a fixed point of that shrinking, and then consider dilations by factors completely unrelated to the shrinking you started. There is no a priori reason why those would actually be inside the polygon. (Again, the more detailed solution below does address this issue, but not yours.) $\endgroup$
    – Boris Bukh
    Oct 10, 2014 at 2:08
8
$\begingroup$

Let $\ L\ $ be a Hilbert space. Let $\ P\subseteq L\ $ be a non-empty compact subset. Then $\ P\ $ is called $\ \mu$-shrinkable $\ \Leftarrow:\Rightarrow$

$$\exists_{q\in L}\ \ \mu\cdot P\ +\ q\ \subseteq\ P$$

for arbitrary $\ \mu\ge 0\ $ (thus $\ \mu \le 1\ $ when $\ |P|>1$).

Let $\ m(P)\ $ be the set of all $\ \mu\ge 0\ $ such that $\ P\ $ is $\ \mu$-shrinkable. Following @E.S.Halevi, let $\ P\ $ be called shrinkable $\ \Leftarrow:\Rightarrow\ \ m(P) = [0;1].\ $ Then

THEOREM  The following three properties of a non-empty compact $\ P\subseteq L\ $are equivalent:

  1. P is a star set;
  2. P is shrinkable;
  3. $\ \sup (\ m(P)\cap[0;1)\ )\ =\ 1$

PROOF   Implications $\ 1\Rightarrow 2\Rightarrow 3\ $ are trivial. we need only $\ 3\Rightarrow 1.\ $ Thus assume condition $3$.

Consider map $\ f_\mu : x\mapsto \mu\cdot x + q_\mu,\ $ of $\ P\ $ into itself, for every $\ \mu\in m(P)\cap[0;1).\ $ Then by Banach's fpp there exists a unique $c_\mu\in P\ $ such that $\ c_\mu = \mu\cdot c_\mu + q_\mu,\ $ so that $\ q_\mu = (1-\mu)\cdot c_\mu.\ $ Thus there is a limit point $\ c_1\in P\ $ of a certain sequence of points $\ c_\mu\ $ for which $ \lim \mu = 1$.

Observe that for $\ \nu:=\mu^k\ $ the composition $\ g_\nu:=\bigcirc^k f_\mu\ $ has the same fixed point (I am going to choose at the most one $\ k\ $ for each $\ \mu;\ $ also

$$\forall_{x\in L}\ \ g_\nu(x)\ =\ \nu\cdot x\ +\ (1-\nu)\cdot c_\mu$$

Now let's consider an arbirary $\ \kappa\in[0;1).\ $ I'll show that function

$$\ F_\kappa\ :\ x\ \mapsto\ \kappa\cdot (x-c_1)+c_1\ \ =\ \ \kappa\cdot x\ +\ (1-\kappa)\cdot c_1$$

maps $\ P\ $ into itself (for every such $\kappa,\ $ so that will be the end of the proof).

Thus let $\ \epsilon > 0.\ $ Then there exist $\ \mu\in[0;1)\ $ and natural $\ k,\ $ such that $\ |c_\mu-c_1|<\epsilon\ $ and $\ |\nu-\kappa|<\epsilon\ $ for $\ \nu:=\mu^k,\ $ hence for arbitrary $\ x\in P$:

$$ |g_\nu(x)-F_\kappa(x)|\ \le\ |g_\nu(x)-F_\nu(x)|\ +\ |F_\nu(x)-F_\kappa(x)|$$

where

$$\ |F_\nu(x)-F_\kappa(x)|\ =\ |(\nu-\kappa)\cdot x + (\kappa-\nu)\cdot c_1|\ =\ |\nu-\kappa|\cdot|x-c_1|$$

henceforth

$$|F_\nu(x)-F_\kappa(x)|\ \le\ \epsilon\cdot |x-c_1|$$

Next

$$|g_\nu(x)-F_\nu(x)|\ =\ |(1-\nu)\cdot c_\mu - (1-\nu)\cdot c_1|\ =\ |1-\nu|\cdot|c_\mu-c_1|\ \le\ \epsilon$$

These inequalities imply:

$$ |g_\nu(x)-F_\kappa(x)|\ \le\ (|x-c_1|+1)\cdot\epsilon$$

or

$$ |g_\nu(x)-F_\kappa(x)|\ \le\ D\cdot\epsilon$$

where  $\ D := diam(P)$

Thus for every $\ \delta > 0\ $ let $\ \epsilon:=\frac\delta D\ $ such that... OK, enough of this $\delta$-$\epsilon$ business, $\ F_\kappa(x)\in P$.

END of PROOF

REMARK The theorem holds not just for the Hilbert spaces but also for Banach spaces. One should be also able to replace translations by arbitrary linear isometries. I am even curious and hopeful about considering this kind of theorems for the locally convex linear spaces.

$\endgroup$
6
  • 1
    $\begingroup$ Looks fine now. I delete my earlier comments. $\endgroup$ Oct 7, 2014 at 11:38
  • $\begingroup$ Willie, you are very kind. You didn't have to delete them, it was still ok, you have provided an essential service to me, so nice. In general, I have a hard time to edit my solutions since two different parts of my brain are involved (one does the solving, the other one the editing; the latter one is careless, sloppy, chaotic, irresponsible, etc, etc--more so than the former one). $\endgroup$ Oct 7, 2014 at 11:47
  • $\begingroup$ I'm a bit confused about why one can find $\mu$ and $k$ such that $\mu^k$ is arbitrarily close to the chosen $\kappa$. Would you mind elaborating on that? Thank you! $\endgroup$ Oct 7, 2014 at 18:18
  • $\begingroup$ Here, @Harry, please: Let $\ 1-\mu < \epsilon\ $ for certain $\ \mu\in(0;1).\ $ Let $\ N\ $ be such that $\ \mu^N<\epsilon\ $. (I'll just continue below). $\endgroup$ Oct 7, 2014 at 20:11
  • 1
    $\begingroup$ Ah, OK. I see it now -- let me elaborate what's missing here; the difference between adjacent powers of $\mu$ is at most $1-\mu$. So if $1-\mu<\varepsilon$, then powers of $\mu$ are less than $\varepsilon$ apart, so $\kappa$ must lie within $\varepsilon$ of one of them. (Thank you again!) $\endgroup$ Oct 8, 2014 at 16:09
1
$\begingroup$

Here is my variant, a bit more geometrical.

Denote by $P$ the original polygon, and $P_\lambda$ the contracted polygon with a factor $\lambda \in (0,1)$ which lies inside $P$. Note that $P_\lambda$ is obtained from $P$ after a dilation and a translation, and therefore there exists a point $O_\lambda$ such that $P_\lambda$ is the image of $P$ under a homothety $h_\lambda$ of center $O_\lambda$ and factor $\lambda$.

Now we know that $h_\lambda : P \to P_\lambda \subset P$ is well defined, continuous and a contraction. Therefore, since $P$ is closed, $h_\lambda$ has a fixed point in $P$, which can only be $O_\lambda$. As a consequence $O_\lambda \in P\cap P_\lambda$.

Pick a sequence $\lambda_n \to 1$ and denote $O_n = O_{\lambda_n}$. Since $(O_n)$ is contained in a compact set $P$, it follows that it has at least one limit point $O$. For keeping the notations simple, we assume the whole $(O_n)$ is convergent to $O$.

Take now $X \in P$ and assume that $[OX]$ is not contained in $P$. Then there exists $Y \in [OX] \setminus P$. Since $P$ is closed, there exists a maximal open subsegment $(X_1X_2)$ of $[OX]$ which contains $Y$ and is out of $P$ ($X_1 \in (OY)$). Obviously $X_1,X_2 \in P$. Moreover, there exists an open cone $C$ of direction given by $(X_1X_2)$, with angle and length $\varepsilon$ small enough, which contains $(X_1X_2)\cap B(X_2,\varepsilon)$ and does not intersect $P$. This happens since $P$ is a polygon and the exterior of $P$ near $X_2$ is either an angle or a half-plane. Consider now $Z_n = h_{\lambda_n}(X_2)$. By hypothesis we have $(Z_n) \subset P$.

Since $O_n \to O$, for $n$ large enough the angle $\angle O_nX_2O$ will be smaller than $\varepsilon/2$. Since $O_nZ_n = \lambda_n O_nX_2$ and $\lambda_n \to 1$ the points $Z_n$ will lie in the cone $C$ for $n$ large enough. This contradicts the fact that $Z_n$ is in $P$.

Therefore $P$ is star-shaped with respect to $O$.

$\endgroup$
0
$\begingroup$

If I understand the question correctly the requirement is for a figure, F, such there exists a translation T(c) for all contractions c, such that cF+T(c) lies within F. It seems to me that that criterion holds for monoconvex hexagons (chevrons) and biconvex hexagons (hourglasses), which are not stars.

$\endgroup$
1
  • 2
    $\begingroup$ They may not be "stars" but they are star-shaped with respect to certain points. For the chevron, you may take the point to be the vertex that the chevron "points towards", and for the hourglass, you may take the point to be the centroid of the shape. $\endgroup$
    – j.c.
    Jul 23, 2015 at 16:53

Your Answer

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

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