Point in Polytope?

808 Views Asked by At

Context: This question is somewhat identical to this on MathOverflow, it’s different in that it only focuses on the formula of the solution to the underlying problem.


Suppose I have a convex hull $H$ from the $\mathbb{R}^n$ vertices of a polytope. What is the formula to determine whether a point $p$ is contained within the polytope (convex hull $H$)?

1

There are 1 best solutions below

6
On

Assume the vertices that span the convex hull are $v_1,v_2,\dots,v_k\in\mathbb{R}^n$ with coordinates $$ v_i = (v_{i1},v_{i2},\dots,v_{in}). $$

A point $p\in\mathbb{R}^n$ lies in the convex hull if and only if there exists $\lambda_1,\dots,\lambda_k\geq 0$ with $\sum \lambda_j = 1$ satisfying $$ \sum_{j=1}^k \lambda_j v_j = p. $$

Let $V$ be the $n\times k$ matrix with columns $v_1,v_2,\dots,v_k$, so the above equation can be written as $$ V\lambda = p $$ where $\lambda$ denotes the (column) vector $(\lambda_1,\dots,\lambda_k)$. Add the row $(1,1,\dots,1)$ to $V$ to get the matrix $V'$, so $V'$ has the form $$ V' = \begin{bmatrix} v_{11} & v_{21} & \dots & v_{k1}\\ v_{12} &\ddots & &\vdots \\ \vdots & &\ddots &\vdots \\ v_{1n} & & & v_{kn}\\ 1 & 1 & \dots & 1 \end{bmatrix}. $$

Then, $p$ is in the convex hull if and only if there exists a $\lambda\in\mathbb{R}^k$ satisfying $$ V'\lambda=\begin{bmatrix} p\\ 1 \end{bmatrix},\qquad\text{and}\qquad \lambda\geq 0. $$ This is a linear program and you can check if it is feasible using linear programming algorithms.