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