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

[Simon Brenner]

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?

// Simon

On 6/6/07, Ilya Tsindlekht <eilya497 at 013.net> wrote:
> On Wed, Jun 06, 2007 at 12:23:03PM +1200, Daniel McAllansmith wrote:
> > Hello.
> >
> > I've got a system of linear inequalities representing half-spaces.  The
> > half-spaces may or may not form a convex hull.
> >
> > I need to find the integral coordinates that are contained within the convex
> > hull, if there is one.
> >
> > For example, given
> > 0 <= x <= 4
> > 0 <= y <= 3
> > 0 <= 2x - y
> > 0 <= 1.2y - x
> >
> > I want the following (x,y) coordinates
> > [(0,0),(1,1),(1,2),(2,2),(2,3),(3,3)]
> >
> >
> > Anybody have any suggestions, or libraries, for solving this in many
> > dimensions and equations?
> >
> >
> If I am not mistaken, this problem is called integer programming and it is NP-complete
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>