3
$\begingroup$

I have a set S of high dimensional points in Euclidean space, with convex hull H (not known); and some target point T in that space not in or on H.

Rather than worry about calculating both H and the distance to it explicitly, is there an efficient way to calculate just the distance from T to the closest point on H? I was thinking something involving binary space partitioning with spitting planes, but can't quite figure out how to formulate the approach (esp. which planes to choose).

Improve this question
$\endgroup$
  • 1
    $\begingroup$ As far as I can see, this approach would only work (to give an exact result) if you managed to get a (possibly translated version) of the tangent hyperplane associated to $H$ and $T$. I fail to understand how to obtain said hyperplane without working with (parts of) $H$. $\endgroup$ – Watercrystal Oct 22 '20 at 3:14

Your Answer

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

Browse other questions tagged or ask your own question.