[Haskell-cafe] Finding points contained within a convex hull.
Ilya Tsindlekht
eilya497 at 013.net
Wed Jun 6 04:12:56 EDT 2007
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
More information about the Haskell-Cafe
mailing list