0
$\begingroup$

If I have a point in 3-space, as well as a convex 3-polytope, and an unordered set of distances to the vertices of the 3-polytope (but not the position of these vertices) is there any way for me to determine if the point is inside the polytope? If not, what if we restrict the polytope to be a 3-simplex?

$\endgroup$
0
$\begingroup$

No, not even for a 3-simplex. Take our point to be the origin, and let $a<b<c<d$ be the distances from the origin to vertices of your 3-simplex. We will construct two polytopes with the specified distances, one with the origin inside the polytope, and one with the origin outside the polytope. Let $\varepsilon>0$ be sufficiently small.

  • Let $A$ be a point on the line from the origin in the direction $(1,0,\pm \varepsilon)$ of length $a$
  • Let $B$ be a point on the line from the origin in the direction $(-1,1,\pm\varepsilon)$ of length $b$
  • Let $C$ be a point on the line from the origin in the direction $(-1,-1,\pm\varepsilon)$ of length $c$
  • Let $D$ be a point on the line from the origin in the direction $(0,0,1)$ of length $d$.

Now, depending on if we choose the signs $\pm$ to all be positive or all negative, the origin is either outisde or inside the polytope which is the convex hull of $A,B,C,D$.

$\endgroup$
  • $\begingroup$ What if we have the closest distances to the triangular faces of the 3-polytope? $\endgroup$ – John Apr 18 '13 at 18:12
  • $\begingroup$ @John: A similar construction should work, but I don't have an exact answer right now. The main obstacle you have for what you want to do is that intuitively, it should be possible to construct polytopes with all possible ratios $b/a,c/a,d/a$, and then it is just a matter of scaling the polytope to get any possible $a,b,c,d$. If you don't know anything about the size of your polytope (its diameter as a subset of $\mathbb R^3$, for instance), it is hopeless to determine if a point is inside or outside. $\endgroup$ – Samuel Apr 18 '13 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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