### 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*).

report62.ps.gz