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?

  • 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. – djechlin Oct 2 '14 at 8:02
  • 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. – Erel Segal-Halevi Oct 2 '14 at 8:05
  • 1
    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? – Per Alexandersson Oct 2 '14 at 8:16
  • 2
    @PerAlexandersson I don't have such an example. I believe that being star-shaped is necessary, but I don't have a proof. – Erel Segal-Halevi Oct 2 '14 at 8:20
  • 1
    Tangentially related: "Shrink polygon to a specific area by offsetting." – Joseph O'Rourke Oct 2 '14 at 12:03
up vote 27 down vote accepted

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

  • Why do you need to assume that the original polygon is simply-connected? – Erel Segal-Halevi Oct 2 '14 at 8:55
  • 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. – Gabriel C. Drummond-Cole Oct 2 '14 at 9:01
  • 1
    Thanks. It is gladdening to have a necessary condition that matches the sufficient condition. – Erel Segal-Halevi Oct 2 '14 at 16:37
  • 2
    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?) – Boris Bukh Oct 7 '14 at 14:33
  • 2
    @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.) – Boris Bukh Oct 10 '14 at 2:08

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.

  • Thank you, @Willie, you are right. However, I think, this my faulty uniqueness was an artifact--I wanted it simple to write too much. I think I can fix it. About $\lambda$, I am actually using it (unless you found a particular typo). – Włodzimierz Holsztyński Oct 7 '14 at 10:48
  • Yes, I fixed that $\lambda$, I was/am tired, thank you again. But the proof is fine. I fixed some faults, I'll check it now and later for the rest of any problems--I think that they are trivial. Thank you for your patience, so helpful to me. – Włodzimierz Holsztyński Oct 7 '14 at 11:19
  • 1
    Looks fine now. I delete my earlier comments. – Willie Wong Oct 7 '14 at 11:38
  • 1
    The $\cup$ near the beginning of the proof needs to be a $\cap$. – S. Carnahan Oct 7 '14 at 13:45
  • 1
    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!) – Harry Altman Oct 8 '14 at 16:09

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

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.

  • 2
    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. – j.c. Jul 23 '15 at 16:53

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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