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/