(*Algorithm to find vertices of a polyhedron discussed in Lecture 5*)
findVertices[A_,b_]:=(
(*Input is A and b such that the polyhedron S is made of x such that A.x ≤ b*)
(*Matrix A is m x n, so there are m affine inequalities a_i x ≤ b_i that define S, and x is a vector with n coordinates*)
{m,n}=Dimensions[A];
rows=Subsets[Range[m],{n}];(*Subsets of {1,..,m} with n elements*)
vertices={};(*Start with the empty list and run a for loop to add vertices*)
For[i=1,i≤Binomial[m,n],i++,(*Loop discussed in lecture has 3 steps*)
If[Det[A[[rows[[i]]]]]≠0,(*step (i)*)
v=LinearSolve[A[[rows[[i]]]],b[[rows[[i]]]]]];(*step (ii)*)
If[VectorLessEqual[{A.v,b}],
vertices=Join[vertices,{v}]];(*step (iii)*)
];
(*Output are the vertices of polyhedron S*)
Return[Union[vertices]];
);
(*Plot the results*)
plotPolygon[A_,b_,xmax_,ymax_]:=(
X=Array[x,n];
plotS=RegionPlot[And@@Table[A[[i]].X≤b[[i]],{i,1,m}],{x[1],-1,xmax},{x[2],-1,ymax}];
plotVert=ListPlot[vertices,PlotStyle->{Thick,Red}];
Return[Show[plotS,plotVert]]
);

A={{-1,0},{0,-1},{1,1}};
b={0,0,1};
findVertices[A,b]
plotPolygon[A,b,2,2]

A={{2,4},{1,1},{0,1},{1,-1},{-1,0},{0,-1}};
b={12,5,5/2,4,0,0};
findVertices[A,b]
plotPolygon[A,b,5,3]

(*Higher dimensional example, with random numbers*)
m=10;
n=5;
A=RandomReal[{-5,5},{m,n}];
b=RandomReal[{-5,5},{m}];
findVertices[A,b]
Length[%]

(*Challenge question: what is the expected number of vertices if A and b are sampled from uniform distributions?*)