AbstractWe 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
- Selim G. Akl and Godfried T. Toussaint. A fast convex hull algorithm. Information Processing Letters, 7(5):219-222, August 1978.
- Bernard Chazelle. An optimal convex hull algorithm and new results on cuttings (extended abstract). In 32nd Annual Symposium on Foundations of Computer Science, pages 29-38, San Juan, Puerto Rico, 1-4 October 1991. IEEE.
- Kenneth L. Clarkson. A Las Vegas algorithm for linear programming when the dimension is small. In 29th Annual Symposium on Foundations of Computer Science, pages 452-456, White Plains, New York, 24-26 October 1988. IEEE.
- Kenneth L. Clarkson. More output-sensitive geometric algorithms (extended abstract). In 35th Annual Symposium on Foundations of Computer Science, pages 695-702, Santa Fe, New Mexico, 20-22 November 1994. IEEE.
- David P. Dobkin and Steven P. Reiss. The complexity of linear programming. Theoretical Computer Science, 11(1):1-18, May 1980.
- M. E. Dyer. Linear time algorithms for two- and three-variable linear programs. SIAM Journal on Computing, 13(1):31-45, February 1984.
- Herbert Edelsbrunner and Weiping Shi. An O(n log^2 h) time algorithm for the three-dimensional convex hull problem. SIAM Journal on Computing, 20(2):259-269, April 1991.
- R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1(4):132-133, June 1972.
- Michael Kallay. Convex hull made easy. Information Processing Letters, 22(3):161, 3 March 1986.
- David G. Kirkpatrick and Raimund Seidel. The ultimate planar convex hull algorithm? SIAM Journal on Computing, 15(1):287-299, February 1986.
- Nimrod Megiddo. Linear programming in linear time when the dimension is fixed. Journal of the ACM, 31(1):114-127, January 1984.
- Thomas Ottmann, S. Schuierer, and S. Soundaralakshmi. Enumerating extreme points in higher dimensions. In 12th Annual Symposium on Theoretical Aspects of Computer Science, volume 900 of Lecture Notes in Computer Science, pages 562-570, Munich, Germany, 2-4 March 1995. Springer.
- Mark H. Overmars and Jan van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23(2):166-204, October 1981.
- Micha Sharir and Emo Welzl. A combinatorial bound for linear programming and related problems. In 9th Annual Symposium on Theoretical Aspects of Computer Science, volume 577 of Lecture Notes in Computer Science, pages 569-579, Cachan, France, 13-15 February 1992. Springer.