{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T15:25:55Z","timestamp":1760369155473},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642401039"},{"type":"electronic","value":"9783642401046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40104-6_43","type":"book-chapter","created":{"date-parts":[[2013,7,11]],"date-time":"2013-07-11T05:36:30Z","timestamp":1373520990000},"page":"499-511","source":"Crossref","is-referenced-by-count":5,"title":["Dynamic Planar Point Location with Sub-logarithmic Local Updates"],"prefix":"10.1007","author":[{"given":"Maarten","family":"L\u00f6ffler","sequence":"first","affiliation":[]},{"given":"Joseph A.","family":"Simons","sequence":"additional","affiliation":[]},{"given":"Darren","family":"Strash","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"43_CR1","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: Proc. 39th Symp. on Foundations of Computer Science, pp. 534\u2013543 (1998)","DOI":"10.7146\/brics.v5i16.21956"},{"key":"43_CR2","doi-asserted-by":"crossref","unstructured":"Arge, L., Brodal, G.S., Georgiadis, L.: Improved dynamic planar point location. In: Proc. 47th Symp. on Foundations of Computer Science, pp. 305\u2013314 (2006)","DOI":"10.1109\/FOCS.2006.40"},{"key":"43_CR3","unstructured":"Bentley, J.L.: Solutions to Klee\u2019s rectangle problems. Technical report, Carnegie-Mellon Univ., Pittsburgh, PA (1977)"},{"issue":"3","key":"43_CR4","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/S0022-0000(05)80059-5","volume":"48","author":"M. Bern","year":"1994","unstructured":"Bern, M., Eppstein, D., Gilbert, J.: Provably good mesh generation. J.\u00a0Comput. Syst. Sci.\u00a048(3), 384\u2013409 (1994)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"5","key":"43_CR5","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1137\/0221057","volume":"21","author":"S.W. Cheng","year":"1992","unstructured":"Cheng, S.W., Janardan, R.: New results on dynamic planar point location. SIAM J. Comput.\u00a021(5), 972\u2013999 (1992)","journal-title":"SIAM J. Comput."},{"key":"43_CR6","unstructured":"Berg, M.d., Gray, C.: Vertical ray shooting and computing depth orders for fat objects. In: SODA, pp. 494\u2013503. ACM Press (2006)"},{"issue":"2","key":"43_CR7","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0205015","volume":"5","author":"D.P. Dobkin","year":"1976","unstructured":"Dobkin, D.P., Lipton, R.J.: Multidimensional searching problems. SIAM J. Comput.\u00a05(2), 181\u2013186 (1976)","journal-title":"SIAM J. Comput."},{"key":"43_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00288933","volume":"4","author":"R.A. Finkel","year":"1974","unstructured":"Finkel, R.A., Bentley, J.L.: Quad trees: A data structure for retrieval on composite keys. Acta Inform.\u00a04, 1\u20139 (1974)","journal-title":"Acta Inform."},{"key":"43_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/3-540-57568-5_243","volume-title":"Algorithms and Computation","author":"R. Fleischer","year":"1993","unstructured":"Fleischer, R.: A simple balanced search tree with o(1) worst-case update time. In: Ng, K.W., Balasubramanian, N.V., Raghavan, P., Chin, F.Y.L. (eds.) ISAAC 1993. LNCS, vol.\u00a0762, pp. 138\u2013146. Springer, Heidelberg (1993)"},{"issue":"3","key":"43_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1541885.1541889","volume":"5","author":"Y. Giora","year":"2009","unstructured":"Giora, Y., Kaplan, H.: Optimal dynamic vertical ray shooting in rectilinear planar subdivisions. ACM Trans. Algorithms\u00a05(3), 28:1\u201328:51 (2009)","journal-title":"ACM Trans. Algorithms"},{"key":"43_CR11","doi-asserted-by":"crossref","unstructured":"Husfeldt, T., Rauhe, T.: Lower bounds for dynamic transitive closure, planar point location, and parentheses matching. Nordic J. Computing\u00a03 (1996)","DOI":"10.7146\/brics.v3i9.19972"},{"key":"43_CR12","doi-asserted-by":"crossref","unstructured":"L\u00f6ffler, M., Simons, J.A., Strash, D.: Dynamic planar point location with sub-logarithmic local updates. Arxiv report, arXiv:1204.4714 [cs.CG] (April 2012)","DOI":"10.1007\/978-3-642-40104-6_43"},{"key":"43_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-540-69903-3_14","volume-title":"Algorithm Theory \u2013 SWAT 2008","author":"Y. Nekrich","year":"2008","unstructured":"Nekrich, Y.: Data structures with local update operations. In: Gudmundsson, J. (ed.) SWAT 2008. LNCS, vol.\u00a05124, pp. 138\u2013147. Springer, Heidelberg (2008)"},{"key":"43_CR14","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"Sarnak, N., Tarjan, R.E.: Planar point location using persistent search trees. Commun. ACM\u00a029, 669\u2013679 (1986), \n                  \n                    http:\/\/doi.acm.org\/10.1145\/6138.6151\n                  \n                  \n                , doi:10.1145\/6138.6151","journal-title":"Commun. ACM"},{"issue":"4","key":"43_CR15","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0925-7721(96)00016-8","volume":"9","author":"M. Kreveld van","year":"1998","unstructured":"van Kreveld, M.: On fat partitioning, fat covering, and the union size of polygons. Comput. Geom. Theory Appl.\u00a09(4), 197\u2013210 (1998)","journal-title":"Comput. Geom. Theory Appl."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40104-6_43","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T18:26:08Z","timestamp":1557944768000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40104-6_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642401039","9783642401046"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40104-6_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}