I am looking for the most efficient algorithm to use to, given a set of points in $d$ dimensional space, find the normals of the convex hull of these points, given that I know that the number of unique facets is going to be fairly low. As far as I understand, the default implementation of QuickHull in qhull is not at all efficient for this type of problem if $d$ is above 10, so I was wondering if anyone was aware of a better approach to this problem.


A secondary problem is searching only for the subset of facet normals that satisfy some linear constraints - it does not seem that it would be feasible to do so without enumerating all the polytope normals, but if I am mistaken here, I would be very happy to hear about it!


Thank you!



Efficient algorithm for finding normals of a high dimensional convex hull with few facets
See Avis' lrs software suite (its predecessor cdd has rather mysterious complexity properties): <http://cgm.cs.mcgill.ca/~avis/doc/avis/Av98a.pdf>


