{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:29:04Z","timestamp":1760441344922},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,5,17]],"date-time":"2016-05-17T00:00:00Z","timestamp":1463443200000},"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":[[2016,12]]},"DOI":"10.1007\/s00454-016-9784-4","type":"journal-article","created":{"date-parts":[[2016,5,17]],"date-time":"2016-05-17T15:04:56Z","timestamp":1463497496000},"page":"866-881","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings"],"prefix":"10.1007","volume":"56","author":[{"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[]},{"given":"Konstantinos","family":"Tsakalidis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,5,17]]},"reference":[{"key":"9784_CR1","doi-asserted-by":"crossref","unstructured":"Afshani, P., Chan, T.M.: Optimal halfspace range reporting in three dimensions. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201909, pp. 180\u2013186. SIAM, Philadelphia (2009)","DOI":"10.1137\/1.9781611973068.21"},{"key":"9784_CR2","doi-asserted-by":"crossref","unstructured":"Afshani, P., Chan, T.M., Tsakalidis, K.: Deterministic rectangle enclosure and offline dominance reporting on the RAM. In: Proceedings of the the Forty-First International Colloquium on Automata, Languages and Programming, ICALP\u201914. LNCS, vol. 8572, pp. 77\u201388. Springer, Berlin (2014)","DOI":"10.1007\/978-3-662-43948-7_7"},{"key":"9784_CR3","doi-asserted-by":"crossref","unstructured":"Afshani, P., Tsakalidis, K.: Optimal deterministic shallow cuttings for 3d dominance ranges. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201914, pp. 1389\u20131398. SIAM, Portland (2014)","DOI":"10.1137\/1.9781611973402.102"},{"issue":"1","key":"9784_CR4","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF02187805","volume":"5","author":"PK Agarwal","year":"1990","unstructured":"Agarwal, P.K.: Partitioning arrangements of lines I: an efficient deterministic algorithm. Discrete Comput. Geom. 5(1), 449\u2013483 (1990)","journal-title":"Discrete Comput. Geom."},{"key":"9784_CR5","volume-title":"Intersection and Decomposition Algorithms for Planar Arrangements","author":"PK Agarwal","year":"1991","unstructured":"Agarwal, P.K.: Intersection and Decomposition Algorithms for Planar Arrangements. Cambridge University Press, New York (1991)"},{"issue":"3","key":"9784_CR6","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/PL00009348","volume":"19","author":"PK Agarwal","year":"1998","unstructured":"Agarwal, P.K., Aronov, B., Chan, T.M., Sharir, M.: On levels in arrangements of lines, segments, planes, and triangles. Discrete Comput. Geom. 19(3), 315\u2013331 (1998)","journal-title":"Discrete Comput. Geom."},{"key":"9784_CR7","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Jacob, R.: Dynamic planar convex hull with optimal query time. In: Proceedings of the Seventh Scandinavian Workshop on Algorithm Theory, SWAT\u201900, pp. 57\u201370 (2000)","DOI":"10.1007\/3-540-44985-X_7"},{"key":"9784_CR8","doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Jacob, R.: Dynamic planar convex hull. In: Proceedings of the Forty-Third Symposium on Foundations of Computer Science, FOCS\u201902, pp. 617\u2013626. IEEE, Vancouver (2002)","DOI":"10.1109\/SFCS.2002.1181985"},{"issue":"2","key":"9784_CR9","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1137\/S0097539798349188","volume":"30","author":"TM Chan","year":"2000","unstructured":"Chan, T.M.: Random sampling, halfspace range reporting, and construction of $$({\\le }k)$$ ( \u2264 k ) -levels in three dimensions. SIAM J. Comput. 30(2), 561\u2013575 (2000)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9784_CR10","doi-asserted-by":"crossref","first-page":"879","DOI":"10.1137\/S0097539703439404","volume":"34","author":"TM Chan","year":"2005","unstructured":"Chan, T.M.: Low-dimensional linear programming with violations. SIAM J. Comput. 34(4), 879\u2013893 (2005)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9784_CR11","first-page":"16:1","volume":"57","author":"TM Chan","year":"2010","unstructured":"Chan, T.M.: A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. J. ACM 57(3), 16:1\u201316:15 (2010)","journal-title":"J. ACM"},{"issue":"04","key":"9784_CR12","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1142\/S0218195912600096","volume":"22","author":"TM Chan","year":"2012","unstructured":"Chan, T.M.: Three problems about dynamic convex hulls. Int. J. Comput. Geom. Appl. 22(04), 341\u2013364 (2012)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9784_CR13","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 Twenty-Seventh Symposium on Computational Geometry, SoCG\u201911, pp. 1\u201310. ACM, New York (2011)","DOI":"10.1145\/1998196.1998198"},{"issue":"2","key":"9784_CR14","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(2), 703\u2013729 (2009)","journal-title":"SIAM J. Comput."},{"key":"9784_CR15","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Tsakalidis, K.: Optimal deterministic algorithms for 2-d and 3-d shallow cuttings. In: Proceedings of the Thirty-First Annual Symposium on Computational Geometry, SoCG\u201915, pp. 719\u2013732. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2015)","DOI":"10.1007\/s00454-016-9784-4"},{"issue":"1","key":"9784_CR16","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B Chazelle","year":"1993","unstructured":"Chazelle, B.: Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom. 9(1), 145\u2013158 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"9784_CR17","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF02122778","volume":"10","author":"B Chazelle","year":"1990","unstructured":"Chazelle, B., Friedman, J.: A deterministic view of random sampling and its use in geometry. Combinatorica 10(3), 229\u2013249 (1990)","journal-title":"Combinatorica"},{"key":"9784_CR18","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."},{"issue":"1","key":"9784_CR19","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1137\/0213003","volume":"13","author":"ME Dyer","year":"1984","unstructured":"Dyer, M.E.: Linear time algorithms for two- and three-variable linear programs. SIAM J. Comput. 13(1), 31\u201345 (1984)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"9784_CR20","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"GN Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput. 16(6), 1004\u20131022 (1987)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9784_CR21","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1006\/jcss.1995.1076","volume":"51","author":"MT Goodrich","year":"1995","unstructured":"Goodrich, M.T.: Planar separators and parallel polygon triangulation. J. Comput. Syst. Sci. 51(3), 374\u2013389 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"9784_CR22","unstructured":"Har-Peled, S., Kaplan, H., Sharir, M., Smorodinsky, S.: Epsilon-nets for halfspaces revisited. CoRR http:\/\/arxiv.org\/abs\/1410.3154 (2014)"},{"issue":"1","key":"9784_CR23","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: $$\\varepsilon $$ \u03b5 -nets and simplex range queries. Discrete Comput. Geom. 2(1), 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"9784_CR24","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"issue":"1","key":"9784_CR25","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/BF02187804","volume":"5","author":"J Matou\u0161ek","year":"1990","unstructured":"Matou\u0161ek, J.: Construction of $$\\varepsilon $$ \u03b5 -nets. Discrete Comput. Geom. 5(1), 427\u2013448 (1990)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"9784_CR26","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF02574697","volume":"6","author":"J Matou\u0161ek","year":"1991","unstructured":"Matou\u0161ek, J.: Cutting hyperplane arrangements. Discrete Comput. Geom. 6(1), 385\u2013406 (1991)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"9784_CR27","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0925-7721(92)90006-E","volume":"2","author":"J Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J.: Reporting points in halfspaces. Comput. Geom. 2(3), 169\u2013186 (1992)","journal-title":"Comput. Geom."},{"issue":"4","key":"9784_CR28","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/PL00009394","volume":"20","author":"J Matou\u0161ek","year":"1998","unstructured":"Matou\u0161ek, J.: On constants for cuttings in the plane. Discrete Comput. Geom. 20(4), 427\u2013448 (1998)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"9784_CR29","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1137\/0212052","volume":"12","author":"N Megiddo","year":"1983","unstructured":"Megiddo, N.: Linear-time algorithms for linear programming in $${R}^3$$ R 3 and related problems. SIAM J. Comput. 12(4), 759\u2013776 (1983)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9784_CR30","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/2422.322418","volume":"31","author":"N Megiddo","year":"1984","unstructured":"Megiddo, N.: Linear programming in linear time when the dimension is fixed. J. ACM 31(1), 114\u2013127 (1984)","journal-title":"J. ACM"},{"key":"9784_CR31","doi-asserted-by":"crossref","unstructured":"Ramos, E.A.: On range reporting, ray shooting and $$k$$ k -level construction. In: Proceedings of the Fifteenth Annual Symposium on Computational Geometry, SoCG\u201999, pp. 390\u2013399. ACM, New York (1999)","DOI":"10.1145\/304893.304993"},{"key":"9784_CR32","doi-asserted-by":"crossref","unstructured":"Ramos, E.A.: Deterministic algorithms for 3-d diameter and some 2-d lower envelopes. In: Proceedings of the Sixteenth Annual Symposium on Computational Geometry, SoCG\u201900, pp. 290\u2013299. ACM, New York (2000)","DOI":"10.1145\/336154.336215"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-016-9784-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-016-9784-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-016-9784-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-016-9784-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,24]],"date-time":"2022-06-24T04:20:57Z","timestamp":1656044457000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-016-9784-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,17]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,12]]}},"alternative-id":["9784"],"URL":"https:\/\/doi.org\/10.1007\/s00454-016-9784-4","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,17]]}}}