An analogue of the Krein-Milman theorem for star-shaped sets

Horst Martini and Walter Wenzel

Abstract: Motivated by typical questions from computational geometry (visibility and art gallery problems) and combinatorial geometry (illumination problems) we present an analogue of the Krein-Milman theorem for the class of star-shaped sets. If $S\subseteq\mathbb{R}^n$ is compact and star-shaped, we consider a fixed, nonempty, compact, and convex subset $K$ of the convex kernel $K_0=\mbox{ck}(S)\mbox{ of }S$, for instance $K=K_0$ itself. A point $q_0\in S\setminus K$ will be called an extreme point of $S$ modulo $K$, if for all $p\in S\setminus(K\cup\{q_0\})$ the convex closure of $K\cup\{p\}$ does not contain $q_0$. We study a closure operator $\sigma:{\cal P}(\mathbb{R}^n\setminus K)\longrightarrow{\cal P} (\bR^n\setminus K)$ induced by visibility problems and prove that $\sigma(S_0)=S\setminus K$, where $S_0$ denotes the set of extreme points of $S$ modulo $K$.

Keywords: convex sets, star-shaped sets, closure operators, Krein-Milman theorem, visibility problems, illumination problems, watchman route problem, $d$-dimensional volume

Classification (MSC2000): 52A30; 06A15, 52-01, 52A20, 52A43

Full text of the article:

• Compressed PostScript file (72 kilobytes)
• PDF file (156 kilobytes)