{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:44:48Z","timestamp":1725795888626},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_7","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T12:10:36Z","timestamp":1402488636000},"page":"77-88","source":"Crossref","is-referenced-by-count":5,"title":["Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM"],"prefix":"10.1007","author":[{"given":"Peyman","family":"Afshani","sequence":"first","affiliation":[]},{"given":"Timothy M.","family":"Chan","sequence":"additional","affiliation":[]},{"given":"Konstantinos","family":"Tsakalidis","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"7_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-540-87744-8_4","volume-title":"Algorithms - ESA 2008","author":"P. Afshani","year":"2008","unstructured":"Afshani, P.: On dominance reporting in 3D. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol.\u00a05193, pp. 41\u201351. Springer, Heidelberg (2008)"},{"doi-asserted-by":"crossref","unstructured":"Afshani, P., Tsakalidis, K.: Optimal deterministic shallow cuttings for 3D dominance ranges. In: Proc. of the 25th An. SODA, pp. 1389\u20131398. ACM-SIAM (2014)","key":"7_CR2","DOI":"10.1137\/1.9781611973402.102"},{"issue":"7","key":"7_CR3","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1109\/TC.1980.1675628","volume":"29","author":"J.L. Bentley","year":"1980","unstructured":"Bentley, J.L., Wood, D.: An optimal worst case algorithm for reporting intersections of rectangles. IEEE Trans. Computers\u00a029(7), 571\u2013577 (1980)","journal-title":"IEEE Trans. Computers"},{"issue":"2","key":"7_CR4","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/s00453-007-9062-1","volume":"50","author":"T.M. Chan","year":"2008","unstructured":"Chan, T.M.: All-pairs shortest paths with real weights in O(n\n                  3\/log n) time. Algorithmica\u00a050(2), 236\u2013243 (2008)","journal-title":"Algorithmica"},{"issue":"3","key":"7_CR5","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/2483699.2483702","volume":"9","author":"T.M. Chan","year":"2013","unstructured":"Chan, T.M.: Persistent predecessor search and orthogonal point location on the word RAM. ACM Transactions on Algorithms\u00a09(3), 22 (2013)","journal-title":"ACM Transactions on Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., P\u0103tra\u015fcu, M.: Orthogonal range searching on the RAM, revisited. In: Proc. of the 27th SoCG, pp. 1\u201310. ACM (2011)","key":"7_CR6","DOI":"10.1145\/1998196.1998198"},{"issue":"2","key":"7_CR7","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/07068669X","volume":"39","author":"T.M. Chan","year":"2009","unstructured":"Chan, T.M., P\u0103tra\u015fcu, M.: Transdichotomous results in computational geometry, I: Point location in sublogarithmic time. SIAM J. Comp.\u00a039(2), 703\u2013729 (2009)","journal-title":"SIAM J. Comp."},{"doi-asserted-by":"crossref","unstructured":"Chan, T.M., P\u0103tra\u015fcu, M.: Counting inversions, offline orthogonal range counting, and related problems. In: Proc. of the 21st An. SODA, pp. 161\u2013173. ACM-SIAM (2010)","key":"7_CR8","DOI":"10.1137\/1.9781611973075.15"},{"issue":"2","key":"7_CR9","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01840440","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B., Guibas, L.J.: Fractional cascading: I. A data structuring technique. Algorithmica\u00a01(2), 133\u2013162 (1986)","journal-title":"Algorithmica"},{"issue":"3","key":"7_CR10","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","volume":"48","author":"M.L. Fredman","year":"1994","unstructured":"Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comp. Syst. Sci.\u00a048(3), 533\u2013551 (1994)","journal-title":"J. Comp. Syst. Sci."},{"issue":"3","key":"7_CR11","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1006\/jcss.1995.1076","volume":"51","author":"M.T. Goodrich","year":"1995","unstructured":"Goodrich, M.T.: Planar separators and parallel polygon triangulation. J. Comp. Syst. Sci.\u00a051(3), 374\u2013389 (1995)","journal-title":"J. Comp. Syst. Sci."},{"issue":"5","key":"7_CR12","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1142\/S0218195997000260","volume":"7","author":"P. Gupta","year":"1997","unstructured":"Gupta, P., Janardan, R., Smid, M., DasGupta, B.: The rectangle enclosure and point-dominance problems revisited. I. J. C. Geom. & Appl.\u00a07(5), 437\u2013455 (1997)","journal-title":"I. J. C. Geom. & Appl."},{"issue":"1","key":"7_CR13","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.jalgor.2003.09.001","volume":"50","author":"Y. Han","year":"2004","unstructured":"Han, Y.: Deterministic sorting in O(nloglogn) time and linear space. J. Algorithms\u00a050(1), 96\u2013105 (2004)","journal-title":"J. Algorithms"},{"issue":"5-6","key":"7_CR14","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0020-0190(99)00145-3","volume":"72","author":"G. Lagogiannis","year":"1999","unstructured":"Lagogiannis, G., Makris, C., Tsakalidis, A.K.: A new algorithm for rectangle enclosure reporting. Inf. Process. Lett.\u00a072(5-6), 177\u2013182 (1999)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"7_CR15","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0196-6774(82)90021-9","volume":"3","author":"D.T. Lee","year":"1982","unstructured":"Lee, D.T., Preparata, F.P.: An improved algorithm for the rectangle enclosure problem. J. Algorithms\u00a03(3), 218\u2013224 (1982)","journal-title":"J. Algorithms"},{"issue":"3","key":"7_CR16","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comp.\u00a09(3), 615\u2013627 (1980)","journal-title":"SIAM J. Comp."},{"key":"7_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/978-3-642-35261-4_59","volume-title":"Algorithms and Computation","author":"C. Makris","year":"2012","unstructured":"Makris, C., Tsakalidis, K.: An improved algorithm for static 3D dominance reporting in the pointer machine. In: Chao, K.-M., Hsu, T.-s., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol.\u00a07676, pp. 568\u2013577. Springer, Heidelberg (2012)"},{"key":"7_CR18","doi-asserted-by":"publisher","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. Comp. Geom.\u00a02, 169\u2013186 (1992)","journal-title":"Comp. Geom."},{"doi-asserted-by":"crossref","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry - An Introduction. Springer (1985)","key":"7_CR19","DOI":"10.1007\/978-1-4612-1098-6"},{"doi-asserted-by":"crossref","unstructured":"Ramos, E.A.: On range reporting, ray shooting and k-level construction. In: Proc. of the 15th SoCG, pp. 390\u2013399. ACM (1999)","key":"7_CR20","DOI":"10.1145\/304893.304993"},{"issue":"4","key":"7_CR21","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1016\/0146-664X(80)90034-9","volume":"13","author":"V. Vaishnavi","year":"1980","unstructured":"Vaishnavi, V., Wood, D.: Data structures for the rectangle containment and enclosure problems. Comp. Graphics and Image Processing\u00a013(4), 372\u2013384 (1980)","journal-title":"Comp. Graphics and Image Processing"},{"issue":"1","key":"7_CR22","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1976","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Mathematical Systems Theory\u00a010(1), 99\u2013127 (1976)","journal-title":"Mathematical Systems Theory"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T22:17:07Z","timestamp":1558909027000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}