Star shaped which is not convex

Question

How to prove that there exists a star-shaped set $ B ⊆ \mathbb{R}^n$ that is not convex. By picture it is pretty much clear that a star figure is star shaped which is not convex, but how to construct in $\mathbb{R}^n$.

Answer 1

In general most Voronoi regions in $\mathbb{R}^n$ induced by the $L_1$ norm or by the $L_{\infty}$ norm are star-shaped but not convex. (On the other hand those induced by $L_2$ are always convex).

For instance:

If you are unfamiliar with Voronoi regions, they represent a partition of the space by closest distance to each center (the black dots). Every point within a region may be "seen" from the center, but 45 degree pockets may form under $L_1$ and $L_\infty$ metrics.

Non-Convex Example

For an explicit example, consider $L_1$ on $\mathbb{R}^n$ with $p_1=(-1, 1,0,\dotsc)$ and $p_2=(1,-1,0,\dotsc)$, projecting the first two dimensions, the boundary looks like this

The regions are given by $$R_1 = \{\, p\in\mathbb{R}^n \colon \|p-p_1\|_1 \leq \|p-p_2\|_1 \,\} \quad\text{and}\quad R_2 = \{\, p\in\mathbb{R}^n \colon \|p-p_2\|_1 \leq \|p-p_1\|_1 \,\}$$

Let $q_1 = (0,0,0,\dotsc), q_2=(1,\tfrac12,0,\dotsc)$. These points fall on the boundary as $$\|q_1-p_1\|_1=\|q_1-p_2\|_1=2$$ $$\|q_2-p_1\|_1=\|q_2-p_2\|_1=2.5$$ Hence $q_1, q_2 \in R_1\cap R_2$, but the point in the middle, $q_m = \tfrac12(q_1+q_2) = (\tfrac12, \tfrac14, 0, \dotsc)$, satisfies

$$\|q_m-p_1\|_1 = \tfrac94 $$ $$\|q_m-p_2\|_1 = \tfrac74$$ hence $q_m\in R_2$, but $q_m\not\in R_1$ so $R_1$ is not convex.

Proof Norm-Induced Voronoi Regions are Star Shaped We'll deal only with the two point case, but the $n$ point case follows by intersecting all pairwise cases.

Take the center $p_1\in R_1$ and some other point $q \in R_1$. Suppose for the sake of contradiction that there exists some $t \in (0,1)$ such that $r = (1-t)p_1 + t q \not\in R_1$ but $r\in R_2$, then $\|r-p_2\|<\|r-p_1\|$ and so

\begin{align} \|q-p_2\| &\leq \|q-r\| + \|r-p_2\|\\ &< \|q-r\| + \|r-p_1\|\\ &= \left\|q - \big((1-t)p_1 + t q\big)\right\| + \left\|\big((1-t)p_1 + t q\big) - p_1\right\| \\ &= (1-t)\|q-p_1\| + t\|q - p_1\|\\ &= \|q-p_1\| \end{align}

But this would imply $q\in R_2$ not $R_1$, a contradiction.

Answer 2

Take a finite union of a family of lines passing through the origin. A really easy one where you can disprove convexity is $$ B := \big\{(x_1,\ldots,x_n)\in\mathbb{R}^n \,\big|\, \text{at most one $x_i$ is nonzero}\big\}.$$ This is star-shaped with respect to the origin, but it is not convex (unless $n=1$). Indeed, $(2,0,0,\ldots,0)$ and $(0,2,0,0,\ldots,0)$ both belong to $B$ but their midpoint $(1,1,0,0,\ldots,0)$ does not.