If $P$ is a set of $n$ points in the euclidean plane whose convex hull $\operatorname{CH}(P)$ has $h$ corners, and $Q\subset P$ has $m\le\lfloor\frac{h}{2}\rfloor$ points and maximal sum of pairwise distances between its elements among all subsets of $P$ with $m$ points,
is it true that the convex hull $\operatorname{CH}(Q)$ of $Q$ has no edge in common with $\operatorname{CH}(P)$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
No: for $m\ge 2$, take $P$ as $h$ points on a short circular arc. The set $Q$ will alway contain the first and the last point along the arc, which form an edge of the convex hull of $P$.