Closest point of a simplex to a random point
in [Matlab]
|
Prev: help for image restore
Next: MATLAB Dynamic tooltips
From: Matt J on 5 Jun 2010 18:25 "Bruno Luong" <b.luong(a)fogale.findmycountry> wrote in message <huei5f$eld$1(a)fred.mathworks.com>... > "Bruno Luong" <b.luong(a)fogale.findmycountry> wrote in message <huear3$h5a$1(a)fred.mathworks.com>... > > > > QP is iterative but converge in finite number of steps (I believe it's NP hard problem theoretically, but who care at only 3 variables). A well implemented method (anti cycling, etc...) will find the constraints set without exploring them all (i.e., 14 for 4 constraints). > > I would add that there are actually 2^4 = 16 possible number of active sets for 4 constraints. But because the tetrahedron is not empty, and because the point is outside it, two of the 16 actives sets (no constraint and all 4 active constraints) never occur. Which makes the count 14. ========= I would add also that a few active sets can be ruled out fairly immediately. Assume, without loss of generality, that the point external to the tetradhedron is the origin. The problem and its constraints can then be represented in the form min ||x||^2 A*x<=b; %suppose the rows of A are normalized to have unit norm so that the values of b(i) will contain the distances to all the faces. You can then rule out all but the minimum b(i). Similarly, you can rule out all but the minimum norm vertex. So, that drops the search down from 14 to 8 active sets. |