{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,31]],"date-time":"2025-03-31T21:04:00Z","timestamp":1743455040554},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540590422"},{"type":"electronic","value":"9783540491750"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59042-0_105","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:59:45Z","timestamp":1330257585000},"page":"562-570","source":"Crossref","is-referenced-by-count":15,"title":["Enumerating extreme points in higher dimensions"],"prefix":"10.1007","author":[{"given":"Th.","family":"Ottmann","sequence":"first","affiliation":[]},{"given":"S.","family":"Schuierer","sequence":"additional","affiliation":[]},{"given":"S.","family":"Soundaralakshmi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"P. Agarwal and J. Matousek. Ray shooting and parametric search. In Proc. 21st ACM Symp. on Theory of Computing, pages 517\u2013526, 1992.","key":"49_CR1","DOI":"10.1145\/129712.129763"},{"issue":"5","key":"49_CR2","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0020-0190(78)90003-0","volume":"7","author":"S. G. Akl","year":"1978","unstructured":"S. G. Akl and G. T. Toussaint. A fast convex hull algorithm. Information Processing Letters, 7(5):219\u2013222, 1978.","journal-title":"Information Processing Letters"},{"key":"49_CR3","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1016\/0262-8856(83)90065-3","volume":"1","author":"B. K. Bhattacharya","year":"1983","unstructured":"B. K. Bhattacharya and G. T. Toussaint. Time-and storage-efficient implementation of an optimal convex hull algorithm. Image Vision Computing, 1:140\u2013144, 1983.","journal-title":"Image Vision Computing"},{"key":"49_CR4","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1090\/dimacs\/004\/07","volume":"4","author":"K. H. Borgwardt","year":"1991","unstructured":"K. H. Borgwardt, N. Gaffke, M. J\u00fcnger, and G. Reinelt. Computing the convex hull in the euclidean plane in linear expected time. In Applied Geometry and Discrete Mathematics THE VICTOR KLEE FESTSCHRIFT, pages 91\u2013107. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 4, 1991.","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"B. Chazelle. An optimal convex hull algorithm and new results on cuttings. In Proc. 32nd IEEE Symp. on Foundations of Computer Science, pages 29\u201338, 1991.","key":"49_CR5","DOI":"10.1109\/SFCS.1991.185345"},{"unstructured":"B. Chazelle. Optimal algorithms for computing depths and layers. In Proc. 21st Allerton Conference on Communication, Control and Computation, pages 427\u2013436, 1983.","key":"49_CR6"},{"key":"49_CR7","volume-title":"Linear Programming","author":"V. Chv\u00e1tal","year":"1983","unstructured":"V. Chv\u00e1tal. Linear Programming. W. H. Freeman, New York, NY, 1983."},{"doi-asserted-by":"crossref","unstructured":"K. L. Clarkson. A Las Vegas algorithm for linear programming when the dimension is small. In Proc. 29th IEEE Symp. on Foundations of Computer Science, pages 452\u2013456, 1988.","key":"49_CR8","DOI":"10.1109\/SFCS.1988.21961"},{"key":"49_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(80)90031-6","volume":"11","author":"D. P. Dobkin","year":"1980","unstructured":"D. P. Dobkin and S. P. Reiss. The complexity of linear programming. Theoretical Computer Science, 11:1\u201318, 1980.","journal-title":"Theoretical Computer Science"},{"key":"49_CR10","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1137\/0213003","volume":"13","author":"M. E. Dyer","year":"1984","unstructured":"M. E. Dyer. Linear time algorithms for two-and three-variable linear programs. SIAM Journal of Computing, 13:31\u201345, 1984.","journal-title":"SIAM Journal of Computing"},{"key":"49_CR11","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1137\/0220016","volume":"20","author":"H. Edelsbrunner","year":"1991","unstructured":"H. Edelsbrunner and W. Shi. An O(n log2 h) time algorithm for the three-dimensional convex hull problem. SIAM Journal of Computing, 20:259\u2013277, 1991.","journal-title":"SIAM Journal of Computing"},{"doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer Verlag, EATCS Monographs on Theoretical Computer Science Edition, 1987.","key":"49_CR12","DOI":"10.1007\/978-3-642-61568-9"},{"key":"49_CR13","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R. L. Graham","year":"1972","unstructured":"R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1:132\u2013133, 1972.","journal-title":"Information Processing Letters"},{"key":"49_CR14","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1007\/BF02218436","volume":"23","author":"G. H. Johansen","year":"1983","unstructured":"G. H. Johansen and C. Gram. A simple algorithm for building the 3-d convex hull. BIT, 23:146\u2013160, 1983.","journal-title":"BIT"},{"key":"49_CR15","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0020-0190(86)90064-5","volume":"22","author":"M. Kallay","year":"1986","unstructured":"M. Kallay. Convex hull made easy. Information Processing Letters, 22:161\u2013163, 1986.","journal-title":"Information Processing Letters"},{"key":"49_CR16","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0215021","volume":"15","author":"D. G. Kirkpatrick","year":"1986","unstructured":"D. G. Kirkpatrick and R. Seidel. The ultimate planar convex hull algorithm? SIAM Journal of Computing, 15:287\u2013299, 1986.","journal-title":"SIAM Journal of Computing"},{"doi-asserted-by":"crossref","unstructured":"J. Matousek and O. Schwarzkopf. Linear optimization queries. In Proc. 8th ACM Symp. on Computational Geometry, pages 16\u201325, 1992.","key":"49_CR17","DOI":"10.1145\/142675.142683"},{"key":"49_CR18","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N. Megiddo","year":"1984","unstructured":"N. Megiddo. Linear programming in linear time when the dimension is fixed. Journal of the ACM, 31:114\u2013127, 1984.","journal-title":"Journal of the ACM"},{"key":"49_CR19","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M. Overmars","year":"1981","unstructured":"M. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23:166\u2013204, 1981.","journal-title":"Journal of Computer and System Sciences"},{"unstructured":"E. Welzl and R. Seidel, referred to in [17], p. 25.","key":"49_CR20"},{"key":"49_CR21","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/BF00535300","volume":"2","author":"A. R\u00e9nyi","year":"1963","unstructured":"A. R\u00e9nyi and R. Sulanke. \u00dcber die konvexe H\u00fclle von n zuf\u00e4llig gew\u00e4hlten Punkten. Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und Verwandte Gebiete, 2:75\u201384, 1963.","journal-title":"Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und Verwandte Gebiete"},{"key":"49_CR22","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1007\/BF02574699","volume":"6","author":"R. Seidel","year":"1991","unstructured":"R. Seidel. Small-dimensional linear programming and convex hulls made easy. Discrete & Computational Geometry, 6:423\u2013434, 1991.","journal-title":"Discrete & Computational Geometry"},{"doi-asserted-by":"crossref","unstructured":"M. Sharir and E. Welzl. A combinatorial bound for linear programming and related problems. In Proc. 9th Symp. on Theoretical Aspects Computer Science, LNCS 577, pages 569\u2013579. Springer-Verlag, 1992.","key":"49_CR23","DOI":"10.1007\/3-540-55210-3_213"}],"container-title":["Lecture Notes in Computer Science","STACS 95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59042-0_105.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:25:08Z","timestamp":1605630308000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59042-0_105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590422","9783540491750"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-59042-0_105","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}