[Haskell-cafe] Finding points contained within a convex hull.

[haskell at list.mightyreason.com]

Simon Brenner wrote:
> Do you simply want the set of coordinates, or do you want to do
> something smart with the them (i.e. optimize a function value etc)?
> 
> In the first case, with a good starting point and a function that
> enumerates all coordinates (by going in a spiral, perhaps), I think
> this can be done in O(nm), where n = number of coordinates in the hull
> and m = number of conditions to be tested for each point. But that all
> depends on the number of coordinates iterated but not in the hull
> being constant, i.e. the number of coordinates iterated but filtered
> out of the set - I have a hunch that that you'll have to factor in the
> number of dimensions somehow - it could well be O(n^dm) or something.
> Oh, and you'll need a terminating condition for the coordinate
> enumerator - and prove that it is correct.
> 
> The latter case is NP-complete ;-) Which might mean that what I said
> above is totally wrong and is also an NP-complete problem.
> 
> Oh, and BTW, isn't any intersection of half-spaces always a convex
> hull? In which case is it not?
> 

If one transforms to get all the extreme vertexes, then you can easily bound
each coordinate by the min and max values of that coordinate in the set of
vertexes.  These bounds on each coordinate give you a large "rectangular" box
that contains your polyhedra.

Brute force testing all the integer coordinates in the box scales as the volume
of the box (some length^d) times the cost of computing the conditions, O(d*m).

Cheers,
  Chris