{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T15:48:14Z","timestamp":1710258494380},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T00:00:00Z","timestamp":1427846400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2015,4]]},"DOI":"10.1007\/s00454-015-9677-y","type":"journal-article","created":{"date-parts":[[2015,4,3]],"date-time":"2015-04-03T06:32:18Z","timestamp":1428042738000},"page":"489-513","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures"],"prefix":"10.1007","volume":"53","author":[{"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[]},{"given":"Patrick","family":"Lee","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,4,2]]},"reference":[{"key":"9677_CR1","doi-asserted-by":"crossref","unstructured":"Afshani, P., Barbay, J., Chan, T.M.: Instance-optimal geometric algorithms. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 129\u2013138 (2009)","DOI":"10.1109\/FOCS.2009.34"},{"key":"9677_CR2","doi-asserted-by":"crossref","first-page":"584","DOI":"10.1137\/S0097539704446724","volume":"37","author":"S Arya","year":"2007","unstructured":"Arya, S., Malamatos, T., Mount, D.M., Wong, K.C.: Optimal expected-case planar point location. SIAM J. Comput. 37, 584\u2013610 (2007)","journal-title":"SIAM J. Comput."},{"key":"9677_CR3","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pp. 80\u201386 (1983)","DOI":"10.1145\/800061.808735"},{"key":"9677_CR4","doi-asserted-by":"crossref","unstructured":"Bentley, J.L., Ottmann, T.A.: Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. C-28(9), 643\u2013647 (1979)","DOI":"10.1109\/TC.1979.1675432"},{"key":"9677_CR5","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/BF02712873","volume":"16","author":"TM Chan","year":"1996","unstructured":"Chan, T.M.: Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete Comput. Geom. 16, 361\u2013368 (1996)","journal-title":"Discrete Comput. Geom."},{"key":"9677_CR6","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/BF02712874","volume":"16","author":"TM Chan","year":"1996","unstructured":"Chan, T.M.: Output-sensitive results on convex hulls, extreme points, and related problems. Discrete Comput. Geom. 16, 369\u2013387 (1996)","journal-title":"Discrete Comput. Geom."},{"key":"9677_CR7","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: Klee\u2019s measure problem made easy. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pp. 410\u2013419 (2013)","DOI":"10.1109\/FOCS.2013.51"},{"issue":"3","key":"9677_CR8","first-page":"22","volume":"9","author":"TM Chan","year":"2013","unstructured":"Chan, T.M.: Persistent predecessor search and orthogonal point location on the word RAM. ACM Trans. Algorithms 9(3), 22 (2013)","journal-title":"ACM Trans. Algorithms"},{"key":"9677_CR9","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s00454-006-1275-6","volume":"37","author":"TM Chan","year":"2007","unstructured":"Chan, T.M., Chen, E.Y.: Multi-pass geometric algorithms. Discrete Comput. Geom. 37, 79\u2013102 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"9677_CR10","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1137\/07068669X","volume":"39","author":"TM Chan","year":"2009","unstructured":"Chan, T.M., P\u01cetra\u015fcu, M.: Transdichotomous results in computational geometry, I: Point location in sublogarithmic time. SIAM J. Comput. 39, 703\u2013729 (2009)","journal-title":"SIAM J. Comput."},{"key":"9677_CR11","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., P\u01cetra\u015fcu, M.: Orthogonal range searching on the RAM, revisited. In: Proceedings of the 27th Annual Symposium on Computational Geometry, pp. 1\u201310 (2011)","DOI":"10.1145\/1998196.1998198"},{"key":"9677_CR12","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/PL00009327","volume":"18","author":"TM Chan","year":"1997","unstructured":"Chan, T.M., Snoeyink, J., Yap, C.K.: Primal dividing and dual pruning: Output-sensitive construction of 4-d polytopes and 3-d Voronoi diagrams. Discrete Comput. Geom. 18, 433\u2013454 (1997)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9677_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/7531.24036","volume":"34","author":"B Chazelle","year":"1987","unstructured":"Chazelle, B., Dobkin, D.P.: Intersection of convex objects in two and three dimensions. J. ACM 34(1), 1\u201327 (1987)","journal-title":"J. ACM"},{"key":"9677_CR14","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0925-7721(94)00018-Q","volume":"5","author":"B Chazelle","year":"1995","unstructured":"Chazelle, B., Matou\u0161ek, J.: Derandomizing an output-sensitive convex hull algorithm in three dimensions. Comput. Geom. Theory Appl. 5, 27\u201332 (1995)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9677_CR15","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/BF01182771","volume":"11","author":"B Chazelle","year":"1994","unstructured":"Chazelle, B., Edelsbrunner, H., Guibas, L.J., Sharir, M.: Algorithms for bichromatic line segment problems and polyhedral terrains. Algorithmica 11, 116\u2013132 (1994)","journal-title":"Algorithmica"},{"key":"9677_CR16","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"KL Clarkson","year":"1987","unstructured":"Clarkson, K.L.: New applications of random sampling in computational geometry. Discrete Comput. Geom. 2, 195\u2013222 (1987)","journal-title":"Discrete Comput. Geom."},{"key":"9677_CR17","doi-asserted-by":"crossref","unstructured":"Clarkson, K.L.: More output-sensitive geometric algorithms. In: Proceedings of the 35th Annual IEEE Symposium Foundations of Computer Science, pp. 695\u2013702 (1994)","DOI":"10.1109\/SFCS.1994.365723"},{"key":"9677_CR18","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"KL Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Applications of random sampling in computational geometry. II. Discrete Comput. Geom. 4, 387\u2013421 (1989)","journal-title":"II. Discrete Comput. Geom."},{"key":"9677_CR19","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1145\/62044.62047","volume":"36","author":"W Cunto","year":"1989","unstructured":"Cunto, W., Munro, J.I.: Average case selection. J. ACM 36, 270\u2013279 (1989)","journal-title":"J. ACM"},{"key":"9677_CR20","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0022-0000(79)90054-0","volume":"18","author":"DP Dobkin","year":"1979","unstructured":"Dobkin, D.P., Lipton, R.J.: On the complexity of computations under varying sets of primitives. J. Comput. Syst. Sci. 18, 86\u201391 (1979)","journal-title":"J. Comput. Syst. Sci."},{"key":"9677_CR21","doi-asserted-by":"crossref","first-page":"1722","DOI":"10.1137\/S0097539795288611","volume":"28","author":"D Dor","year":"1999","unstructured":"Dor, D., Zwick, U.: Selecting the median. SIAM J. Comput. 28, 1722\u20131758 (1999)","journal-title":"SIAM J. Comput."},{"key":"9677_CR22","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1137\/S0895480199353895","volume":"14","author":"D Dor","year":"2001","unstructured":"Dor, D., Zwick, U.: Median selection requires $$(2+\\varepsilon )n$$ ( 2 + \u03b5 ) n comparisons. SIAM J. Discrete Math. 14, 312\u2013325 (2001)","journal-title":"SIAM J. Discrete Math."},{"key":"9677_CR23","doi-asserted-by":"crossref","unstructured":"Dub\u00e9, T.: Dominance range-query: the one-reporting case. In: Proceedings of the 9th Annual ACM Symposium on Computational Geometry, pp. 208\u2013217 (1993)","DOI":"10.1145\/160985.161138"},{"key":"9677_CR24","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s00454-003-0729-3","volume":"31","author":"A Dumitrescu","year":"2004","unstructured":"Dumitrescu, A., Mitchell, J.S.B., Sharir, M.: Binary space partitions for axis-parallel segments, rectangles, and hyperrectangles. Discrete Comput. Geom. 31, 207\u2013227 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"9677_CR25","doi-asserted-by":"crossref","unstructured":"Ford, L.R. jr., Johnson, S.M.: A tournament problem. Am. Math. Monthly 66, 387\u2013389 (1959)","DOI":"10.2307\/2308750"},{"key":"9677_CR26","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0022-0000(82)90048-4","volume":"24","author":"GN Frederickson","year":"1982","unstructured":"Frederickson, G.N., Johnson, D.B.: The complexity of selection and ranking in $$X+Y$$ X + Y and matrices with sorted rows and columns. J. Comput. Syst. Sci. 24, 197\u2013208 (1982)","journal-title":"J. Comput. Syst. Sci."},{"key":"9677_CR27","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1007\/BF01189991","volume":"11","author":"MJ Golin","year":"1994","unstructured":"Golin, M.J.: A provably fast linear-expected-time maxima-finding algorithm. Algorithmica 11, 501\u2013524 (1994)","journal-title":"Algorithmica"},{"key":"9677_CR28","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1137\/0215068","volume":"15","author":"GH Gonnet","year":"1986","unstructured":"Gonnet, G.H., Munro, J.I.: Heaps on heaps. SIAM J. Comput. 15, 964\u2013971 (1986)","journal-title":"SIAM J. Comput."},{"key":"9677_CR29","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"RL Graham","year":"1972","unstructured":"Graham, R.L.: An efficient algorithm for determining the convex hull of a finite planar set. Inf. Process. Lett. 1, 132\u2013133 (1972)","journal-title":"Inf. Process. Lett."},{"key":"9677_CR30","doi-asserted-by":"crossref","first-page":"1380","DOI":"10.1137\/S0097539704445706","volume":"34","author":"J Hershberger","year":"2005","unstructured":"Hershberger, J., Suri, S., T\u00f3th, C.D.: Binary space partitions of orthogonal subdivisions. SIAM J. Comput. 34, 1380\u20131397 (2005)","journal-title":"SIAM J. Comput."},{"key":"9677_CR31","doi-asserted-by":"crossref","unstructured":"Jarvis, R.A.: On the identification of the convex hull of a finite set of points in the plane. Inf. Process. Lett. 2, 18\u201321 (1973)","DOI":"10.1016\/0020-0190(73)90020-3"},{"key":"9677_CR32","doi-asserted-by":"crossref","unstructured":"Kaligosi, K., Mehlhorn, K., Munro, J.I., Sanders, P.: Towards optimal multiple selection. In: Proceedings of the 32nd International Colloquium Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 3580, pp. 103\u2013114. Springer, Heidelberg (2005)","DOI":"10.1007\/11523468_9"},{"key":"9677_CR33","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D.G., Seidel, R.: Output-size sensitive algorithms for finding maximal vectors. In: Proceedings of the 1st Annual ACM Symposium Computational Geometry, pp. 89\u201396 (1985)","DOI":"10.1145\/323233.323246"},{"key":"9677_CR34","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0215021","volume":"15","author":"DG Kirkpatrick","year":"1986","unstructured":"Kirkpatrick, D.G., Seidel, R.: The ultimate planar convex hull algorithm? SIAM J. Comput. 15, 287\u2013299 (1986)","journal-title":"SIAM J. Comput."},{"key":"9677_CR35","unstructured":"Knuth, D.E.: Sorting and Searching. The Art of Computer Programming, vol. 3. Addison-Wesley, Reading (1973)"},{"key":"9677_CR36","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1145\/321906.321910","volume":"22","author":"HT Kung","year":"1975","unstructured":"Kung, H.T., Luccio, F., Preparata, F.P.: On finding the maxima of a set of vectors. J. ACM 22, 469\u2013476 (1975)","journal-title":"J. ACM"},{"key":"9677_CR37","doi-asserted-by":"crossref","unstructured":"Li, Z., Reed, B.A.: Heap building bounds. In: Proceedings of the 9th Workshop Algorithms Data Structures, vol. 3608, pp. 14\u201323. Springer, Heidelberg (2005)","DOI":"10.1007\/11534273_3"},{"issue":"3","key":"9677_CR38","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1137\/S0097539796305365","volume":"28","author":"G Liotta","year":"1998","unstructured":"Liotta, G., Preparata, F.P., Tamassia, R.: Robust proximity queries: an illustration of degree-driven algorithm design. SIAM J. Comput. 28(3), 864\u2013889 (1998)","journal-title":"SIAM J. Comput."},{"key":"9677_CR39","unstructured":"Mehlhorn, K.: Data Structures and Algorithm 1: Sorting and Searching. EATCS Monographs on Theoretical Computer Science, vol. 1. Springer, Heidelberg (1981)"},{"key":"9677_CR40","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"K Mulmuley","year":"1993","unstructured":"Mulmuley, K.: Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, Englewood Cliffs (1993)"},{"key":"9677_CR41","doi-asserted-by":"crossref","unstructured":"Ottmann, T., Schuierer, S., Soundaralakshmi, S.: Enumerating extreme points in higher dimensions. In: Proceedings of the 12th Symposium on Theoretical Aspects of Computer Science. Lecture Notes on Computer Science, vol. 900, pp. 562\u2013570. Springer, Heidelberg (1995)","DOI":"10.1007\/3-540-59042-0_105"},{"key":"9677_CR42","doi-asserted-by":"crossref","first-page":"1034","DOI":"10.1137\/0220065","volume":"20","author":"MH Overmars","year":"1991","unstructured":"Overmars, M.H., Yap, C.-K.: New upper bounds in Klee\u2019s measure problem. SIAM J. Comput. 20, 1034\u20131045 (1991)","journal-title":"SIAM J. Comput."},{"key":"9677_CR43","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0196-6774(92)90007-Y","volume":"13","author":"MS Paterson","year":"1992","unstructured":"Paterson, M.S., Yao, F.F.: Optimal binary space partitions for orthogonal objects. J. Algorithms 13, 99\u2013113 (1992)","journal-title":"J. Algorithms"},{"issue":"3","key":"9677_CR44","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1137\/0210035","volume":"10","author":"FP Preparata","year":"1981","unstructured":"Preparata, F.P.: A new approach to planar point location. SIAM J. Comput. 10(3), 473\u2013482 (1981)","journal-title":"SIAM J. Comput."},{"key":"9677_CR45","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"FP Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985)"},{"key":"9677_CR46","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1006\/jagm.2000.1101","volume":"37","author":"R Seidel","year":"2000","unstructured":"Seidel, R., Adamy, U.: On the exact worst case complexity of planar point location. J. Algorithms 37, 189\u2013217 (2000)","journal-title":"J. Algorithms"},{"key":"9677_CR47","unstructured":"T\u00f3th, C.D.: Binary space partitions: Recent developments. In: Combinatorial and Computational Geometry. MSRI Publications, vol. 52, pp. 525\u2013552. Cambridge University Press, Cambridge (2005)"},{"key":"9677_CR48","doi-asserted-by":"crossref","unstructured":"van Emde Boas, P.: On the $$\\varOmega (n \\log n)$$ \u03a9 ( n log n ) lower-bound for convex hull and maximal vector determination. Inf. Process. Lett. 10, 132\u2013136 (1980)","DOI":"10.1016\/0020-0190(80)90064-2"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9677-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-015-9677-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-015-9677-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,22]],"date-time":"2019-08-22T21:17:39Z","timestamp":1566508659000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-015-9677-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["9677"],"URL":"https:\/\/doi.org\/10.1007\/s00454-015-9677-y","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4]]}}}