Decide inside/outside convex hull using only distances in graph

Question

Given a weighted, undirected graph G with K knodes k1 … kK. I have a K times K matrix containing the shortest distances between each pair of points.

Is it possible (if yes how), to decide if a point lies inside/outside the convex hull of another set of points? I don't have coordinates of the points - only distances between them. If possible, I would like to avoid making any assumptions regarding the dimensionality of the space. If this is unavoidable, let's assume the space is two dimensional.

Answer 1

Assume you want to know if $k_0$ lies in the convex hull of $k_1,\dots,k_n$. Consider the $n\times n$ matrix $A$ with the components $$a_{ij}=(d_{ij}^2-d_{0i}^2-d_{0j}^2)/2$$

(Note that $x^TAx\ge 0$ for any vector $x$; it means that the distances come from Euclidean distances.)

If $x^TAx=0$ for a nonzero vector $x$ with all nonnegative components then the answer is "yes".