1

Let $X = \{x_1,\dotsc,x_n\} \subset \mathbb{R}^2$ be a finite set of points in the plane. No $3$ of them are collinear.

I am trying to think of ways to characterize the convex hull $\operatorname{conv}(X)$. Here is one particular attempt I'm intersted in:

  1. For every vector $v=(x,y)\in\mathbb{R}^2$, write $v^\perp=(-y,x)$.
  2. A pair of indices $1\leq i,j\leq n$ is a maximal pair if $\langle (x_j-x_i)^\perp,x_i\rangle=\max_k\{\langle (x_j-x_i)^\perp,x_k\rangle\}=:t_{i,j}$.
  3. Every maximal pair $i,j$ defines a halfplane $H_{i,j}=\{x\in\mathbb{R}^2\mid\langle (x_j-x_i)^\perp,x\rangle \leq t_{i,j}\}$. Clearly, $X \subset H_{i,j}$.
  4. Let $M$ be the set of maximal pairs. Define $D=\cap_{(i,j)\in M} H_{i,j}$.

Obviously, $D$ is a convex set containing $X$. So, $\operatorname{conv}(X)\subset D$.

Intuitively, it looks like we actually have $\operatorname{conv}(X)=D$. The idea is that the maximal pairs seem to correspond to the sides of the convex hull.

Is $\operatorname{conv}(X)=D$? If so, how can this be proved?

Gils
  • 1,019
  • 8
  • 15
  • You'll need to remove the requirement that $i<j$ to make sure that the half-spaces point in the right direction. Also it won't work if the points are collinear. – p.s. Nov 12 '13 at 05:19
  • @p.s: Ok. I will edit accordingly. – Gils Nov 12 '13 at 07:14
  • To be more specific, it won't work if all the points lie on a single line, because then D would just be that unbounded line. Otherwise I think it's true, but I can't think of a simple proof offhand. – p.s. Nov 12 '13 at 19:02

0 Answers0