0
$\begingroup$

This is not a homework, but a hobby project, and maybe not all terms I use are correct - please help to fix.

Imagine there are K vectors in n-dimensional space. I would like to:

  • validate whether they can correspond to K+1 planes enclosing a volume (is that called a polytope?)
  • validate whether a given further vector is completely inside this polytope, or not.

This might be a well-known multidimensional data search task, but I ask myself:

  • how to formulate the above in "professional" math
  • is this someting I can do nowadays in a high-level way with a standard computational Python SDK like numpy?
$\endgroup$
2

1 Answer 1

3
$\begingroup$

This depends on what you mean by $K$ vectors, and what you mean by corresponding to $K+1$ planes enclosing a volume.

If you mean vectors as arrows all starting at the origin and defining vertex points, then this is essentially finding if

  1. They are linearly independent (Check if the rank of the matrix $\begin{pmatrix}v_1 & \cdots & v_{K} \end{pmatrix}$ is $K$ where $v_j$ are your vectors.)
  2. Find the convex hull of the vectors treated as points (plus the origin). https://en.wikipedia.org/wiki/Convex_hull_algorithms
  3. Check if the new vector (point) is in the convex hull. https://math.stackexchange.com/questions/3206677/how-to-check-if-a-point-is-within-a-convex-hull

If you mean vectors as two points connected by a line segment, this would likely be much harder. You could find the convex hull of all points, but this seems unlikely to be what you mean.

If you mean vectors as points and a normal vector defining planes, then this is also a different problem. For the simplest ($K+1$) sided polytope in K-dimensions these are some necessary conditions:

  1. vectors need to span the space. (Check that the rank of the matrix formed from the vectors is K)
  2. At least one of the K+1 points must be in a separate hyperplane than the remaining points. You could verify this by choosing one point $x_0$ as a reference, then form vectors as $u_i = x_i - x_0$ with the remaining points $x_{1}$ to $x_{K}$ then determine the rank of the matrix $\begin{pmatrix}u_1 & \cdots & u_{K} \end{pmatrix}$ and ensuring that its rank is also $K$
$\endgroup$
1
  • 1
    $\begingroup$ thank you! I think it's first interpretation I have meant, this does help. $\endgroup$ Nov 9, 2022 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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