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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
