Nordic Journal of Computing Bibliography

Thomas Ottmann, Sven Schuierer, and Subbiah Soundaralakshmi. Enumerating Extreme Points in Higher Dimensions. Nordic Journal of Computing, 8(2):179-192, Summer 2001.

We consider the problem of enumerating all extreme points of a given set P of n points in d dimensions. We present a simple and practical algorithm which uses O(n) space and O(nm) time, where m is the number of extreme points of P. Our algorithm is designed to work even for highly degenerate input.

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 time complexity O(n2) which significantly improves the O(n3) complexity of the naive algorithm.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems

Additional Key Words and Phrases: extreme points, linear programming, computational geometry

Selected references


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database