Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 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".

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.