MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

There is a variant of Matus's approach that takes $O(A(T_A + n))$ O(nT_A)$work, where$A\le n$is the size of the answer, that is, the number of extreme points, and$T_A$is the work to solve an LP (or here an SDP) as Matus describes, but for$A+1$points instead of$n$. The algorithm is: (after converting from conic to convex hull) maintain an output set$S$, that starts empty, and test each point$v_i$against$S$one by one. Solve the LP (or SDP) as Matus describes. If$v_i$is an extreme point, include it proven to be in$S$. If the convex hull of$v_i$is not an extreme pointS$, discard it. Otherwise, then the dual certificate gives a direction (at least in the LP case, and something similar should apply in the SDP case) perpendicular to that separating hyperplane, such that the input point that is extreme in that direction is not already in $S$. (While $v_i$ is not in the convex hull of $S$, it may not be extreme itself.) Find that input point and add it to $S$.
There are $A$ iterations,
Testing each requiring an LP or SDP using of the $S$, n$points costs$T_A$, and possibly also the$O(n)$work to find the for finding an extreme point in a given direction yields a new member of$S$, so such tasks need$O(nA)\le O(nT_A)$work. This trick and related ones appeared here ("More output-sensitive..."); the notes for the paper give pointers to some related work. 1 There is a variant of Matus's approach that takes$O(A(T_A + n))$work, where$A\le n$is the size of the answer, that is, the number of extreme points, and$T_A$is the work to solve an LP (or here an SDP) as Matus describes, but for$A+1$points instead of$n$. The algorithm is: maintain an output set$S$, that starts empty, and test each point$v_i$against$S$one by one. Solve the LP (or SDP) as Matus describes. If$v_i$is an extreme point, include it in$S$. If$v_i$is not an extreme point, then the dual certificate gives a direction (at least in the LP case, and something similar should apply in the SDP case) perpendicular to that separating hyperplane, such that the input point that is extreme in that direction is not already in$S$. Find that input point and add it to$S$. There are$A$iterations, each requiring an LP or SDP using$S$, and possibly also the$O(n)\$ work to find the extreme point in a given direction.