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