{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:10:41Z","timestamp":1725455441973},"publisher-location":"Berlin\/Heidelberg","reference-count":18,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540167838"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0016256","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T00:39:17Z","timestamp":1131842357000},"page":"315-324","source":"Crossref","is-referenced-by-count":0,"title":["On the inherent combinatorial complexity of geometric problems in d - dimensional space"],"prefix":"10.1007","author":[{"given":"Th. M.","family":"Fischer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Wolfrum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"27_CR1","unstructured":"D. Avis, Lower bounds for geometric problems, Proc. 18th Allerton Conf. Commun., Contr., Comput. 1980, 35\u201340"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, Lower bounds for algebraic computation trees, Proc. 15th STOC, 1983","DOI":"10.1145\/800061.808735"},{"key":"27_CR3","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/358841.358850","volume":"23","author":"J. L. Bentley","year":"1980","unstructured":"J. L. Bentley, Multidimensional divide-and-conquer, Comm. ACM 23 (1980), 214\u2013229","journal-title":"Comm. ACM"},{"key":"27_CR4","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/BF00263991","volume":"13","author":"J. L. Bentley","year":"1980","unstructured":"J. L. Bentley and H. A. Maurer, Efficient worst case data structures for range searching, Acta Informatica 13 (1980), 155\u2013168","journal-title":"Acta Informatica"},{"key":"27_CR5","unstructured":"Th. Fischer, On the complexity of rectangle intersection problems under structural constraints, Preprint, 1986"},{"key":"27_CR6","unstructured":"Th. Fischer, A note on the combinatorial complexity of the convex hull problem, Preprint (to appear)"},{"key":"27_CR7","volume-title":"Convex Polytopes","author":"B. Gr\u00fcnbaum","year":"1967","unstructured":"B. Gr\u00fcnbaum, Convex Polytopes, Wiley, New York, 1967"},{"key":"27_CR8","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/0020-0190(81)90112-5","volume":"12","author":"J. W. Jaromczyk","year":"1981","unstructured":"J. W. Jaromczyk, Linear decision trees are too weak for convex hull problem, IPL 12 (1981), 138\u2013141","journal-title":"IPL"},{"key":"27_CR9","first-page":"1072","volume":"C-33","author":"D. T. Lee","year":"1984","unstructured":"D. T. Lee and F. P. Preparata, Computational geometry \u2014 a survey, IEEE C-33 (1984), 1072\u20131101","journal-title":"IEEE"},{"key":"27_CR10","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R. J. Lipton","year":"1979","unstructured":"R. J. Lipton, D. J. Rose, R. E. Tarjan, Generalized nested dissection, SIAM J. Num. Anal. 16 (1979), 346\u2013358","journal-title":"SIAM J. Num. Anal."},{"key":"27_CR11","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R. J. Lipton","year":"1980","unstructured":"R. J. Lipton and R. E. Tarjan, Applications of a planar separator theorem, SIAM J. Comp. 9 (1980), 615\u2013627","journal-title":"SIAM J. Comp."},{"key":"27_CR12","doi-asserted-by":"crossref","unstructured":"G. Lueker, A data structure for orthogonal range queries, Proc. 19th FOCS, 1978, 28\u201334","DOI":"10.1109\/SFCS.1978.1"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, Data Structures and Algorithms, Vol. 1\u20133, Springer 1984","DOI":"10.1007\/978-3-642-69900-9_1"},{"key":"27_CR14","first-page":"416","volume":"176","author":"J. Mor\u00e1vek","year":"1984","unstructured":"J. Mor\u00e1vek and P. Pudl\u00e1k, New lower bound for polyhedral membership problem with an application to linear programming, Proc. MFCS'84, LNCS 176 (1984), 416\u2013424","journal-title":"LNCS"},{"key":"27_CR15","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1137\/0208030","volume":"8","author":"L. J. Stockmeyer","year":"1979","unstructured":"L. J. Stockmeyer and C. K. Wong, On the number of comparisons to find the intersection of two relations, SIAM J. Comp. 8 (1979), 388\u2013404","journal-title":"SIAM J. Comp."},{"key":"27_CR16","unstructured":"K. Wolfrum, Time \u2014 optimal algorithms for search problems in d-dimensional spaces, Preprint, 1985"},{"key":"27_CR17","unstructured":"K. Wolfrum, On some search problems in computational geometry, Preprint (to appear)"},{"key":"27_CR18","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1137\/0209028","volume":"9","author":"A. C. Yao","year":"1980","unstructured":"A. C. Yao and R. L. Rivest, On the polyhedral decision problem, SIAM J. Comp. 9 (1980), 343\u2013347","journal-title":"SIAM J. Comp."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1986"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0016256.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T16:35:47Z","timestamp":1607531747000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0016256"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540167838"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/bfb0016256","relation":{},"subject":[]}}