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

[apfelmus]

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