algorithm - How to convert the half-spaces that constitute a convex hull to a set of extreme points? -

algorithm - How to convert the half-spaces that constitute a convex hull to a set of extreme points? -

i have convex set in euclidean space (3d, answers nd) characterized finite set of half-spaces (normal vector + point).

is there improve algorithm find extreme points of convex set other compute brute forcefulness points intersections of 3 (or, n) half-spaces , eliminate not extreme points?

the key term vertex enumeration of polytope p. thought of algorithm described below consider dual polytope p*. vertices of p correspond facets of p*. facets of p* efficiently computed qhull, , remains find vertices solving corresponding sub-systems of linear equations.

the algorithm implemented in bsd-licensed toolset analyze n-dimensional polyhedra in terms of vertices or (in)equalities matlab, authored matt j, specifically, component lcon2vert. however, purpose of reading algorithm , re-implementing language, easier work older , simpler con2vert file michael kleder, matt j's project builds on.

i'll explain step step. individual matlab commands (e.g., convhulln) documented on mathworks site, references underlying algorithms.

the input consists of set of linear inequalities of form ax<=b, matrix , b column vector.

step 1. effort locate interior point of polytope

first seek c = a\b, least-squares solution of overdetermined linear scheme ax=b. if a*c<b holds componentwise, interior point. otherwise, multivariable minimization attempted objective function beingness maximum of 0 , numbers a*c-b. if fails find point a*c-b<0 holds, programme exits "unable find interior point".

step 2. translate polytope origin interior point

this done b = b - a*c in matlab. since 0 interior point, entries of b positive.

step 3. normalize right hand side 1

this partition of ith row of b(i), done d = ./ repmat(b,[1 size(a,2)]); in matlab. on, matrix d used. note rows of d vertices of dual polytope p* mentioned @ beginning.

step 4. check polytope p bounded

the polytope p unbounded if vertices of dual p* lie on same side of hyperplane through origin. detected using built-in function convhulln computes volume of convex hull of given points. author checks whether appending 0 row matrix d increases volume of convex hull; if does, programme exits "non-bounding constraints detected".

step 5. computation of vertices

this loop

for ix = 1:size(k,1) f = d(k(ix,:),:); g(ix,:)=f\ones(size(f,1),1); end

here, matrix k encodes facets of dual polytope p*, each row listing vertices of facet. matrix f submatrix of d consisting of vertices of facet of p*. backslash invokes linear solver, , finds vertex of p.

step 6: clean-up

since polytope translated @ step 2, translation undone v = g + repmat(c',[size(g,1),1]);. remaining 2 lines effort eliminate repeated vertices (not successfully).

algorithm math geometry convex-hull polyhedra