2
$\begingroup$

Is there an efficient way to compute, given a point, the closest point to it that's on the inside of an intersection of half-spaces?

For example, given the half-spaces a & b, the closest point to p that's "inside" the half-spaces is x. + denotes which side is "inside" the half-spaces a and b.

.p
       ^
       |
       |
       | x
   <---.--------------> b
       |       +
       |
       | +
       |
       v a

I'm particularly interested in an algorithm for half-spaces in 3D (planes)

My current line of thinking leads me to have to compute intersections of each half space, and then find the shortest point by picking from the shortest distance to each half-space and each intersection (line, point) that's within all the half-spaces. Is there a better way?

$\endgroup$
2
$\begingroup$

This can be modeled as a convex program $$\begin{align} \text{min.} \qquad & ||x-p||_2^2,\\ \text{s.t.} \qquad & Ax\leq b,\\ & x\in\mathbb{R}^3. \end{align}$$ and solved (in reasonable time) by standard solvers. Here's example code in julia

using Convex, SCS

# generate random problem data
m = 5;  n = 3
A = randn(m,n); b = randn(m,1); p=randn(3,1)

# define problem
x = Variable(n)
problem = minimize(sumsquares(x-p), [A*x<=b])

# solve
solve!(problem, SCSSolver())
println("Status $(problem.status) distance $(problem.optval)")
$\endgroup$
  • $\begingroup$ Are there no properties that we can use here to solve without minimizing/having to model it as a convex program? $\endgroup$ – Danny Yaroslavski Jun 4 at 18:05
  • $\begingroup$ @DannyYaroslavski Possibly, but you will have to reinvent a good part of the techniques that are behind that convex program. As you observe you may have to consider all $m$ halfspaces, all $\binom{m}{2}$ edges, and all $\binom{m}{3}$ extreme points, and an optimal solution can occur in the interior of these sets. $\endgroup$ – Marcus Ritt Jun 4 at 18:14

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.