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

[Daniel McAllansmith]

Thanks for the responses everyone.

On Thursday 07 June 2007 00:37, haskell at list.mightyreason.com wrote:
> 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)?

Ultimately optimise several functions over the feasible coordinates, however 
the functions to optimise are complicated, definitely non-linear, and the 
linear constraints are already a simplification of non-linear constraints.

I was hoping to get a superset of coordinates, filter with the real 
constraints then optimise each of the target functions.


> > Oh, and BTW, isn't any intersection of half-spaces always a convex
> > hull? In which case is it not?

Inconsistent constraints, e.g. x>5, y>5, x+y<10

>
> If one transforms to get all the extreme vertexes, then you can easily
> bound each coordinate by the min and max values of that coordinate in the
> set of vertexes.  These bounds on each coordinate give you a large
> "rectangular" box that contains your polyhedra.

Since Ilya pointed out that integer linear programming is NP-complete I've 
been thinking of determining the bounding-box and doing a branch-and-bound 
search.  My idea was to solve the linear constraints twice for each 
dimension, to maximise and minimise the variable in that dimension.
From there I can divide and conquer, hopefully discarding/fixing whole 
dimensions and reducing the proportion of invalid coordinates.  If need be I 
could even randomly sample the remaining coordinates to keep things 
tractable.

I guess that's not much different from what I was orginally planning - 
superset, filter, optimise... the superset is just bigger now.

How would you go about finding extreme vertices?  Would it be quicker than 
solving the constraints for each max/min?

Thanks
Daniel