Uniformly sampling region defined by linear constraints

I'm trying to uniformly sample the (bounded) feasible region defined by some linear constraints.

At the moment, my plan is to

1. Remove redundant constraints using qhull
2. Find vertices of polytope defined by the non-redundant constraints
3. Use delaunayn to find the unique simplices that make up the polytope
4. Find the volume of each simplex to determine how densely each simplex should be sampled
5. Uniformly sample each simplex according to this scheme

This seems a bit overly complicated. I sort of just mashed together some of the techniques/tools I'm vaguely familiar for this method. Is there a more 'direct' or better way to achieve the same thing?

Note: I intend this for fairly low (<10) dimensional problems. The number of constraints would also likely be low (certainly <20).

Thanks in advance!

Answer 1

[Josh]

I've written a function to do something similar for 1-, 2-, and 3- simplexes (I work mainly with triangle meshes). The approach you outline is roughly what I did...

I think the first 3 steps are possibly redundant. I'm not sure what you're trying to do exactly, but here's my understanding of what the first three steps will do:

(1) Create a convex hull of your inputs. (2) Discard all vertices not on the convex hull. (3) Compute a triangulation of the vertices you have left.

If you skip to step (3), nothing will change except that you may have some vertices included in the triangulation that aren't on the convex hull. It seems like what you're trying to do in steps (4) and (5) is randomly sample the volume of the convex hull. If this is the case, you can skip steps (1) and (2) and get the same result. You may have extra simplexes on the interior, but steps (4) and (5) will handle that fine.

[Edgar]

Ahh, I suspected I was doing too much here. Thanks, Josh!