convex hull interior

Ofer Melnik melnik at
Tue Jan 4 14:39:21 PST 2000


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

Thanks for any help,

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

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list