How to make a star-shaped polygon with some given points

366 Views Asked by At

The problem is about 2D-space.
Each closed curve like $P$, divides the plane into $3$ parts : $P_0$, which is the area inside the curve, $P^c$, which is the area outside the curve, and $P$ itself. ( Jordan Curve Theorem )

Here, when we speak about a polygon, we mean not just the curve $P$, but also $P_0$.

$\forall x,y \in P\cup P_0$, $x$ can see $y$ clearly iff $\overline {xy} \cap P^c = \emptyset \space \land \overline {xy}\cap P\subset\{x,y\}$

For a polygon like $P$, $Kernel(P)$ is a subset of $P_0$ like $S$ such that :
$\forall s \in S \space \forall p \in P\space\space s$ can see $p$ clearly.

A polygon like $P$ is a star-shaped polygon iff $Kernel(P)\neq \emptyset$

The question :
Assume that $n$ points on the plane are given. Provide an algorithm for making a star-shaped polygon in which these points are vertices.

Note : The problem is so easy if the points have a good distance. But i have no idea to solve the problem in general form.

Thanks in advance.