Hello everybody.
I found out the other day something quite astonishing (which I guess
is not astonishing at all to those in the know): in d-dimensional
space, determining whether a given point is inside the convex hull of
a set of n points is elegantly and quickly solvable using linear
programming.
If the columns of matrix "ff" are the coordinates of the set of
points, then in d=2 dimensions with n=4 constraints you can test
whether point "candidate" is inside the convex hull by:
R> candidate <- c(0.2,0.2)
R> a <- rep(1,4)
R> isin <- simplex(a=a, A3=ff, b3 = candidate)
R> #[ff is given below].
Here, simplex() finds the x which minimizes a%*%x subject to ff%*%x candidate
[this works fine; candidate is inside the convex hull
generated by the origin and the four points specified by the columns
of ff because sum(isin$soln) <= 1].
However, sometimes (for d=27,n=2000) a feasible starting vector is
hard to find. So, if the constraint is changed to an inequality,
everything should still work. Here, we need to set A2 and b2 (rather
than A3 and b3):
R> simplex(a=a, A2=ff, b2 = candidate)
but then I get an error:
R> simplex(a=rep(1,4),A2=ff,b2=candidate)
Error in rbind(iden(m1), zero(m2 + m3, m1)) :
attempt to set an attribute on NULL
R>
What's going on here? surely switching A3 => A2 and b3 => b2 should
still work?
simplex() seems to stop because "rbind(NULL,NULL)" returns an error
(but I can't quite work out if rbind() is reasonable or not, given
that c(NULL,NULL) is OK).
R> dput (ff)
structure(c(-0.282700887536384, -0.691284233263613, 3.07385122964501,
1.63593735251412, -0.130733385680257, 0.290532564591650, -1.14808732324176,
-0.338686094983058), .Dim = c(2, 4))>
--
Robin Hankin, Lecturer,
School of Geography and Environmental Science
Tamaki Campus
Private Bag 92019 Auckland
New Zealand
r.hankin at auckland.ac.nz
tel 0064-9-373-7599 x6820; FAX 0064-9-373-7042
as of: Wed Sep 25 13:57:00 NZST 2002
This (linux) system up continuously for: 391 days, 20 hours, 39 minutes
-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
r-help mailing list -- Read http://www.ci.tuwien.ac.at/~hornik/R/R-FAQ.html
Send "info", "help", or "[un]subscribe"
(in the "body", not the subject !) To: r-help-request at
stat.math.ethz.ch
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._