Technical Report No. 62, November 1994 - Abstract

Thomas Ottmann, Sven Schuierer, Subbiah Soundaralakshmi:
Enumerating Extreme Points in Higher Dimensions

We consider the problem of enumerating all extreme points of a given set P of n points in d dimensions. We present an algorithm with O(n) space and O(n*m) time where m is the number of extreme points of P.

We also present an algorithm to compute the depth of each point of the given set of n points in d-dimensions. This algorithm has complexity O(n^2) which significantly improves the O(n^3) complexity of the previously best known deterministic algorithm. It also improves the best known randomized algorithm with expected running time O(n^{3-(2/(1+|.d/2.|))} + delta)
(for any fixed delta > 0).