{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T12:08:32Z","timestamp":1775650112207,"version":"3.50.1"},"reference-count":45,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1985,3,1]],"date-time":"1985-03-01T00:00:00Z","timestamp":478483200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Algorithms"],"published-print":{"date-parts":[[1985,3]]},"DOI":"10.1016\/0196-6774(85)90017-3","type":"journal-article","created":{"date-parts":[[2005,2,10]],"date-time":"2005-02-10T08:44:36Z","timestamp":1108025076000},"page":"17-48","source":"Crossref","is-referenced-by-count":70,"title":["Finding the convex hull facet by facet"],"prefix":"10.1016","volume":"6","author":[{"given":"Garret","family":"Swart","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0196-6774(85)90017-3_BIB1","series-title":"The Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"key":"10.1016\/0196-6774(85)90017-3_BIB2","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF02242366","article-title":"An algorithm for enumerating all vertices of a convex polyhedron","volume":"15","author":"Altherr","year":"1975","journal-title":"Computing"},{"key":"10.1016\/0196-6774(85)90017-3_BIB3","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1137\/0109008","article-title":"An algorithm for finding all vertices of convex polyhedral sets","volume":"9","author":"Balinski","year":"1961","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/0196-6774(85)90017-3_BIB4","doi-asserted-by":"crossref","first-page":"349","DOI":"10.2140\/pjm.1973.46.349","article-title":"A proof of the lower bound conjecture for convex polytopes","volume":"46","author":"Barnette","year":"1973","journal-title":"Pacific J. Math."},{"key":"10.1016\/0196-6774(85)90017-3_BIB5","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0020-0190(78)90051-0","article-title":"Divide and conquer for linear expected time","volume":"7","author":"Bentley","year":"1978","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(85)90017-3_BIB6","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1145\/322092.322095","article-title":"On the average number of maxima in a set of vectors and applications","volume":"25","author":"Bentley","year":"1978","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0196-6774(85)90017-3_BIB7","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1090\/S0273-0979-1980-14712-6","article-title":"Sufficiency of McMullen's conditions for f-vectors of simplicial polytopes","volume":"2","author":"Billera","year":"1980","journal-title":"Bull. Amer. Math. Soc. (N.S.)"},{"key":"10.1016\/0196-6774(85)90017-3_BIB8","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0097-3165(81)90058-3","article-title":"A proof of the sufficiency of McMullen's conditions for f-vectors of simplicial convex polytopes","volume":"31","author":"Billera","year":"1981","journal-title":"J. Combin. Theory Ser. A"},{"key":"10.1016\/0196-6774(85)90017-3_BIB9","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1145\/321556.321564","article-title":"An algorithm for convex polytopes","volume":"17","author":"Chand","year":"1970","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/0196-6774(85)90017-3_BIB10","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0020-0190(80)90036-8","article-title":"A note on finding convex hulls via maximal vectors","volume":"11","author":"Devroye","year":"1980","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(85)90017-3_BIB11","unstructured":"M. E. Dyer, The complexity of vertex enumeration methods, manuscript, Department of Mathematics and Statistics, Teesside Polytechnic, Middlesbrough, Cleveland, UK."},{"key":"10.1016\/0196-6774(85)90017-3_BIB12","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF01593771","article-title":"An algorithm for determining all extreme points of a convex polytope","volume":"12","author":"Dyer","year":"1977","journal-title":"Math. Programming"},{"key":"10.1016\/0196-6774(85)90017-3_BIB13_1","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1145\/355759.355766","article-title":"A new convex hull algorithm for planar sets","volume":"3","author":"Eddy","year":"1977","journal-title":"ACM Trans. Math. Software"},{"key":"10.1016\/0196-6774(85)90017-3_BIB13_2","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1145\/355759.355768","article-title":"A new convex hull algorithm for planar sets","volume":"3","author":"Eddy","year":"1977","journal-title":"ACM Trans. Math. Software"},{"key":"10.1016\/0196-6774(85)90017-3_BIB14","series-title":"Technical Report","author":"Friedman","year":"1972"},{"key":"10.1016\/0196-6774(85)90017-3_BIB15","series-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/0196-6774(85)90017-3_BIB16","article-title":"Convex Polytopes","volume":"Vol. XVI","author":"Gr\u00fcnbaum","year":"1967"},{"key":"10.1016\/0196-6774(85)90017-3_BIB17","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","article-title":"An efficient algorithm for determining the convex hull of a finite planar set","volume":"1","author":"Graham","year":"1972","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(85)90017-3_BIB18","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01437214","article-title":"An algorithm for determining redundant inequalities and all solutions to convex polyhedra","volume":"24","author":"Greenberg","year":"1975","journal-title":"Numer. Math."},{"key":"10.1016\/0196-6774(85)90017-3_BIB19","series-title":"Progress in Operations Research","article-title":"Two algorithms for finding all the vertices of a convex polyhdron","author":"Jahanshahlou","year":"1974"},{"key":"10.1016\/0196-6774(85)90017-3_BIB20","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0020-0190(73)90020-3","article-title":"On the identification of the convex hull of a finite set of points in the plane","volume":"2","author":"Jarvis","year":"1973","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0196-6774(85)90017-3_BIB21","first-page":"1093","article-title":"Polynomial algorithm for linear programming","volume":"244","author":"Khachian","year":"1979","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"10.1016\/0196-6774(85)90017-3_BIB22","series-title":"Proceedings IBM Scientific Computing Symposium on Combinatorial Problems","article-title":"Convex polytopes and linear programming","author":"Klee","year":"1966"},{"key":"10.1016\/0196-6774(85)90017-3_BIB23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02392139","article-title":"Polytope pairs and their relationship to linear programming","volume":"133","author":"Klee","year":"1974","journal-title":"Acta Math."},{"key":"10.1016\/0196-6774(85)90017-3_BIB24","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1007\/BF02162916","article-title":"Finding all vertices of a convex polyhedron","volume":"12","author":"Manas","year":"1968","journal-title":"Numer. Math."},{"key":"10.1016\/0196-6774(85)90017-3_BIB25","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1287\/opre.21.1.247","article-title":"An algorithm for determining irrelevant constraints and all vertices in systems of linear inequalities","volume":"21","author":"Mattheiss","year":"1973","journal-title":"Oper. Res."},{"key":"10.1016\/0196-6774(85)90017-3_BIB26","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1287\/moor.5.2.167","article-title":"A survey and comparison of methods for finding all vertices of convex polyhedral sets","volume":"5","author":"Mattheiss","year":"1980","journal-title":"Math. Oper. Res."},{"key":"10.1016\/0196-6774(85)90017-3_BIB27","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1007\/BF01588326","article-title":"Computational results on an algorithm for finding all vertices of a polytope","volume":"18","author":"Mattheiss","year":"1980","journal-title":"Math. Programming"},{"key":"10.1016\/0196-6774(85)90017-3_BIB28","series-title":"Convex Polytopes and the Upper Bound Conjeoture","volume":"Vol. 3","author":"McMullen","year":"1971"},{"key":"10.1016\/0196-6774(85)90017-3_BIB29","series-title":"Solving linear-programming in linear-time when the dimension is fixed, manuscript","author":"Megiddo","year":"1982"},{"key":"10.1016\/0196-6774(85)90017-3_BIB30","series-title":"Proceedings, 23rd Annual Symposium on Foundations of Computer Science","article-title":"On the complexity of unique solutions","author":"Papadimitriou","year":"1982"},{"key":"10.1016\/0196-6774(85)90017-3_BIB31","series-title":"Proceedings, 14th Annual Symposium on Theory of Computation","article-title":"The complexity of facets (and some facets of complexity)","author":"Papadimitriou","year":"1982"},{"key":"10.1016\/0196-6774(85)90017-3_BIB32","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1145\/359423.359430","article-title":"Convex hulls of finite sets of points in two and three dimensions","volume":"20","author":"Preparata","year":"1977","journal-title":"Comm. ACM"},{"key":"10.1016\/0196-6774(85)90017-3_BIB33","doi-asserted-by":"crossref","first-page":"35","DOI":"10.2307\/3212146","article-title":"Sur l'enveloppe convexe des nuages des points aleatoires dans Rn","volume":"7","author":"Raynaud","year":"1970","journal-title":"J. Appl. Probab"},{"key":"10.1016\/0196-6774(85)90017-3_BIB34","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1287\/mnsc.18.7.423","article-title":"Redundant constraints and extraneous variables in integer programs","volume":"18","author":"Rubin","year":"1972","journal-title":"Management Sci."},{"key":"10.1016\/0196-6774(85)90017-3_BIB35","article-title":"A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions","author":"Seidel","year":"1981"},{"key":"10.1016\/0196-6774(85)90017-3_BIB36","unstructured":"R. Seidel, personal communication."},{"key":"10.1016\/0196-6774(85)90017-3_BIB37","article-title":"Computational Geometry","author":"Shamos","year":"1978"},{"key":"10.1016\/0196-6774(85)90017-3_BIB38","article-title":"Reduction of Linear Inequality Constraints and Determination of All Feasible Extreme Points","author":"Shefi","year":"1969"},{"key":"10.1016\/0196-6774(85)90017-3_BIB39","unstructured":"S. Smale, On the average speed of the simplex method of linear programming, manuscript."},{"key":"10.1016\/0196-6774(85)90017-3_BIB40","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1287\/mnsc.12.7.588","article-title":"Techniques for removing nonbinding constraints and extraneous variables from linear programming problems","volume":"12","author":"Thompson","year":"1966","journal-title":"Management Sci."},{"key":"10.1016\/0196-6774(85)90017-3_BIB41","article-title":"Finding Faces of Polytopes by Simplicial Decomposition","author":"von Hohenbalken","year":"1975"},{"key":"10.1016\/0196-6774(85)90017-3_BIB42","doi-asserted-by":"crossref","first-page":"1","DOI":"10.6028\/jres.071B.001","article-title":"Algorithms for frames and lineality spaces of cones","volume":"71B","author":"Wets","year":"1967","journal-title":"J. Res. Nat. Bur. Standards-Bur. Math. Math. Phys."},{"key":"10.1016\/0196-6774(85)90017-3_BIB43","article-title":"A Lower Bound to Finding Convex Hulls","author":"Yao","year":"1979"},{"key":"10.1016\/0196-6774(85)90017-3_BIB44","series-title":"Proceedings, 15th Annual ACM Symposium on Theory of Computation","article-title":"Lower bounds for algebraic computation trees","author":"Ben-Or","year":"1983"}],"container-title":["Journal of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677485900173?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0196677485900173?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,29]],"date-time":"2019-01-29T06:26:30Z","timestamp":1548743190000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0196677485900173"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,3]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,3]]}},"alternative-id":["0196677485900173"],"URL":"https:\/\/doi.org\/10.1016\/0196-6774(85)90017-3","relation":{},"ISSN":["0196-6774"],"issn-type":[{"value":"0196-6774","type":"print"}],"subject":[],"published":{"date-parts":[[1985,3]]}}}