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.
The number of coordinates in the hull is exponential in the number of bits you use to represent those integers. So, the algorithm and NP-completeness don't contradict each other. The situation is similar to the knapsack problem. Regards, apfelmus