convex hull interior

[Ofer Melnik]

Hi,

I was wondering if someone could help me out. I am interested in
algorithms that given a group of red points in n-dimensional space can
answer whether a new blue point is within the interior of the convex hull
defined by the red points. I realize that this can be phrased as a linear
programming problem. But are there specific results on this problem, in
terms of exact and approximate computational complexity? Are there good
algorithms to solve it? Where we know, when they will be efficient and
inefficient?

Thanks for any help,
-Ofer

-----------------------------------------------------------------
Ofer Melnik                         melnik at cs.brandeis.edu
Volen Center for Complex Systems    Ph: (781)-736-2719
Brandeis University                     (781)-736-DEMO
Waltham MA 02254


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://uiuc.edu/~sariel/CG/compgeom/threads.html.