MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|improve this answer

Your Answer


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.