1
$\begingroup$

Let $\mathbb{R}^n$ be a normed affine space of finite dimension $n$, and $d : \mathbb{R}^n \times \mathbb{R}^n \mapsto \mathbb{R}^+$ be the distance derived from the norm under consideration. A convex polytope $P \subseteq \mathbb{R}^n$ is the intersection of any finite number of closed half-spaces from $\mathbb{R}^n$, such that $P \neq \emptyset$. $Pol_n$ denotes the set of all convex polytopes from $\mathbb{R}^n$. A profile $\mathcal{P}$ is a non-empty multiset $\{P_1, \dots, P_k\}$, $k > 0$, of convex polytopes from $Pol_n$. $\mathcal{Pol}_n$ denotes the set of all profiles. $d$ is extended to the mapping $d : \mathbb{R}^n \times Pol_n \mapsto \mathbb{R}^+$ defined $\forall p \in \mathbb{R}^n$, $\forall P \in Pol_n$ as $d(p, P) = \min\{d(p, p') \mid p' \in P\}$. Then, $d$ is extended to the mapping $d : \mathbb{R}^n \times \mathcal{Pol}_n \mapsto \mathbb{R}^+$, defined $\forall p \in \mathbb{R}^n$, $\forall \mathcal{P} \in \mathcal{Pol}_n$ as $d(p, \mathcal{P}) = \sum\{d(p, P) \mid P \in \mathcal{P}\}$.

I would like to show that for any profile $\mathcal{P}$, the set $argmin\{d(p, \mathcal{P}) \mid p \in \mathbb{R}^n\}$ (i.e., the set $\{p \in \mathbb{R}^n \mid \forall p' \in \mathbb{R}^n, d(p, \mathcal{P}) \leq d(p', \mathcal{P})\}$) is a convex polytope (or to find a counter-example, that I failed to do so far).

$\endgroup$
  • $\begingroup$ I am surely misinterpreting your question, but if $\cal P$ consists of just a horizontal segment and a point directly above (but not on) that segment, then $d(p,\cal P)$ has a parabolic ridge (under the Euclidean norm). $\endgroup$ – Joseph O'Rourke May 26 '14 at 16:29
  • $\begingroup$ Sorry if any misunderstanding. I may also misunderstand your counter-example: if you mean that $\mathcal{P}$ is a doubleton consisting of a straight segment $S$ and a point $p$ such that $p \notin S$, then don't we get that $argmin\{d(p', \mathcal{P}) \mid p' \in \mathbb{R}^n\}$ consists in the (unique) segment from $p$ to $argmin\{d(p, s) \mid s \in S\}$? $\endgroup$ – user109711 May 26 '14 at 16:53
  • $\begingroup$ I did misunderstand that argmin expression. Sorry! $\endgroup$ – Joseph O'Rourke May 26 '14 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.