Enumeration Problem: Extreme Points

Remarks:

(a)

The number of output vertices might be exponential in the size of input, while it can be very small. The best upper bound and the best lower bound are both known [McM70, Bar71, DF94].

(b)

Is there any algorithm for the extreme enumeration problem which runs in time polynomial in both the input size and the output size?

(c)

Is there such an algorithm whose space complexity is polynomial in the size of input only?

(d)

The answer to the question (b) is not known in general. When the input is nondegenerate, there are several algorithms. Of course the answer to the question (c) is not known in general. However for the nondegenerate case, the answer is "yes", see the reverse search algorithm [AF92].