1
$\begingroup$

Given a finite set $P$ of $n\gt d+1$ points in $d$-dimensional euclidean space.
Under the assumption that the points of $P$ are in general position in the sense that $\lbrace p_{i_1},\dots,p_{i_d}\rbrace\subset P\implies \alpha_{i_1}p_{i_1}+\cdots+\alpha_{i_d}p_{i_d}\not\in P$:

Question:

is it true that $p_{i_0}\in P$ is inside $P$'s convex hull $CH(P)$, i.e. can be expressed as $p_{i_0}=\sum\limits_{j=1}^{d+1}\alpha_{i_j}p_{i_j},\quad \lbrace p_{i_1},\dots,p_{i_{d+1}}\rbrace\subset P,\,0\lt\alpha_{i_j}\lt 1 \\ \iff \exists\ \lbrace q,t_1,\dots,t_d\rbrace\subset P:\quad(q-p)^T(t_i-p)\lt0\quad\forall i\in\lbrace 1,\dots,d\rbrace$

If that is indeed the case it would be possible find the corners of convex hulls from length measurements alone, making a generalization to arbitrarily weighted complete symmetric graphs possible.

The essential benefit would be having replaced the antisymmetric outer product with the symmetric inner product of vectors.

Another aspect would be that identifying the corners of convex hulls in $d$ dimensional euclidean space would be possible $O(n^3)$ time by iterating over $n$ points as candidates in the role of $p$, $n-1$ further points in the role of $q$ and the remaining $n-2$ points for which the number of negative inner products are counted.

$\endgroup$
2
  • 1
    $\begingroup$ From this post by David Eppstein: "determining whether a given point is a vertex [of the hull] can be done in linear time by solving a linear program" (for fixed dimension $d$). $\endgroup$ Commented Oct 8, 2023 at 12:38
  • $\begingroup$ I'm confused by the statement of your question. Are $q,t_1,\ldots,t_d$ supposed to be a subset of the given points? Is $p$, or is it assumed to be an arbitrary point in $\mathbb{R}^d$? If $q,t_1,\ldots,t_d$ are supposed to be chosen from among the $n$ points, then it seems easy to construct a counterexample by simply drawing a very very small shape and choosing $p$ not too far outside the interior; all possible vectors will have a small length, so their dot products will be less than $1$ no matter which points we pick. $\endgroup$ Commented Oct 8, 2023 at 18:14

0

You must log in to answer this question.

Browse other questions tagged .