From: eppstein@euclid.ics.uci.edu Subject: Re: N-dimensional Space Problem Newsgroups: sci.math Date: 26 Jun 98 19:07:41 GMT > Does anyone know of a method of determining whether or not a point in > N-dimensional space (where N is large, a few hundred) lies inside a cluster > of other points. The inside is defined as the space enclosed by hyperplanes > touching the outer points of the cluster. Ok, let your query point be q, and your cluster points be p_i. Then q is inside the convex hull of the cluster if and only if it is a convex combination of the p_i's -- that is, if there exist values x_i satisfying the constraints 0 <= x_i sum x_i = 1 sum x_i p_i = q This is a system of linear equalities and inequalities, so you should be able to solve it with any linear programming system. Because of the high dimensionality of the problem, I don't think you are likely to find a good solution that avoids linear programming. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/