next up previous
Next: Enumeration Problem: Triangulations Up: Examples of Enumeration Problems Previous: Enumeration Problem: Acyclic Orientations

Enumeration Problem: Extreme Points



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].
Is there any algorithm for the extreme enumeration problem which runs in time polynomial in both the input size and the output size?
Is there such an algorithm whose space complexity is polynomial in the size of input only?
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].

Komei Fukuda
Wed Jun 12 17:26:21 GMT+0100 1996