{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T06:13:22Z","timestamp":1743056002005,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319621265"},{"type":"electronic","value":"9783319621272"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-62127-2_22","type":"book-chapter","created":{"date-parts":[[2017,7,4]],"date-time":"2017-07-04T02:47:31Z","timestamp":1499136451000},"page":"253-264","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["All-Pairs Shortest Paths in Geometric Intersection Graphs"],"prefix":"10.1007","author":[{"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitrios","family":"Skrepetos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,7,5]]},"reference":[{"key":"22_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-662-43948-7_7","volume-title":"Automata, Languages, and Programming","author":"P Afshani","year":"2014","unstructured":"Afshani, P., Chan, T.M., Tsakalidis, K.: Deterministic rectangle enclosure and offline dominance reporting on the RAM. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 77\u201388. Springer, Heidelberg (2014). doi:10.1007\/978-3-662-43948-7_7"},{"issue":"3","key":"22_CR2","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/BF02574385","volume":"12","author":"PK Agarwal","year":"1994","unstructured":"Agarwal, P.K., Alon, N., Aronov, B., Suri, S.: Can visibility graphs be represented compactly? Discrete & Computational Geometry 12(3), 347\u2013365 (1994)","journal-title":"Discrete & Computational Geometry"},{"issue":"4","key":"22_CR3","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1137\/0222050","volume":"22","author":"PK Agarwal","year":"1993","unstructured":"Agarwal, P.K., Pellegrini, M., Sharir, M.: Counting circular arc intersections. SIAM Journal on Computing 22(4), 778\u2013793 (1993)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"22_CR4","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1137\/S0097539796303421","volume":"28","author":"D Aingworth","year":"1999","unstructured":"Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing 28(4), 1167\u20131181 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"Alon, N., Galil, Z., Margalit, O., Naor, M.: Witnesses for boolean matrix multiplication and for shortest paths. In: Proceedings of the Thirty-Third Annual IEEE Symposium on Foundations of Computer Science, pp. 417\u2013426 (1992)","DOI":"10.1109\/SFCS.1992.267748"},{"key":"22_CR6","unstructured":"Blelloch, G.E.: Space-efficient dynamic orthogonal point location, segment intersection, and range reporting. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 894\u2013903 (2008)"},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"Cabello, S.: Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2143\u20132152. SIAM (2017)","DOI":"10.1137\/1.9781611974782.139"},{"issue":"4","key":"22_CR8","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/j.comgeo.2014.12.003","volume":"48","author":"S Cabello","year":"2015","unstructured":"Cabello, S., Jej\u010di\u010d, M.: Shortest paths in intersection graphs of unit disks. Computational Geometry 48(4), 360\u2013367 (2015)","journal-title":"Computational Geometry"},{"issue":"3","key":"22_CR9","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1137\/S009753970343912X","volume":"36","author":"TM Chan","year":"2006","unstructured":"Chan, T.M.: Dynamic subgraph connectivity with geometric applications. SIAM Journal on Computing 36(3), 681\u2013694 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"22_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2344422.2344424","volume":"8","author":"TM Chan","year":"2012","unstructured":"Chan, T.M.: All-pairs shortest paths for unweighted undirected graphs in $$o(mn)$$ time. ACM Transactions on Algorithms 8, 1\u201317 (2012)","journal-title":"ACM Transactions on Algorithms"},{"issue":"3","key":"22_CR11","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/2483699.2483702","volume":"9","author":"TM Chan","year":"2013","unstructured":"Chan, T.M.: Persistent predecessor search and orthogonal point location on the word RAM. ACM Transactions on Algorithms 9(3), 22 (2013)","journal-title":"ACM Transactions on Algorithms"},{"issue":"2","key":"22_CR12","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1006\/jagm.2001.1189","volume":"41","author":"TM Chan","year":"2001","unstructured":"Chan, T.M., Efrat, A.: Fly cheaply: On the minimum fuel consumption problem. Journal of Algorithms 41(2), 330\u2013337 (2001)","journal-title":"Journal of Algorithms"},{"key":"22_CR13","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., P\u0103tra\u015fcu, M.: Orthogonal range searching on the RAM, revisited. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Computational Geometry, pp. 1\u201310 (2011)","DOI":"10.1145\/1998196.1998198"},{"key":"22_CR14","doi-asserted-by":"crossref","unstructured":"Chan, T.M., P\u0103tra\u015fcu, M.: Counting inversions, offline orthogonal range counting, and related problems. In: Proceedings of the Twenty-First Annual ACM-SIAM Aymposium on Discrete Algorithms, pp. 161\u2013173 (2010)","DOI":"10.1137\/1.9781611973075.15"},{"key":"22_CR15","unstructured":"Chan, T.M., Skrepetos, D.: All-pairs shortest paths in unit-disk graphs in slightly subquadratic time. In: Proccedings of the Twenty-Seventh Annual International Symposium on Algorithms and Computation, pp. 24:1\u201324:13 (2016)"},{"issue":"2","key":"22_CR16","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B Chazelle","year":"1993","unstructured":"Chazelle, B.: Cutting hyperplanes for divide-and-conquer. Discrete & Computational Geometry 9(2), 145\u2013158 (1993)","journal-title":"Discrete & Computational Geometry"},{"issue":"4\/5","key":"22_CR17","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0020-0190(81)90053-3","volume":"13","author":"H Edelsbrunner","year":"1981","unstructured":"Edelsbrunner, H., Maurer, H.A.: On the intersection of orthogonal objects. Information Processing Letters 13(4\/5), 177\u2013181 (1981)","journal-title":"Information Processing Letters"},{"issue":"3","key":"22_CR18","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1016\/0020-0190(82)90068-0","volume":"14","author":"H Edelsbrunner","year":"1982","unstructured":"Edelsbrunner, H., Overmars, M.H.: On the equivalence of some rectangle problems. Information Processing Letters 14(3), 124\u2013127 (1982)","journal-title":"Information Processing Letters"},{"issue":"2","key":"22_CR19","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1006\/jcss.1995.1065","volume":"51","author":"T Feder","year":"1995","unstructured":"Feder, T., Motwani, R.: Clique partitions, graph compression and speeding-up algorithms. Journal of Computer and System Sciences 51(2), 261\u2013272 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR20","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF01840357","volume":"2","author":"S Fortune","year":"1987","unstructured":"Fortune, S.: A sweepline algorithm for Voronoi diagrams. Algorithmica 2, 153\u2013174 (1987)","journal-title":"Algorithmica"},{"issue":"3","key":"22_CR21","doi-asserted-by":"publisher","first-page":"28","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 Transactions on Algorithms 5(3), 28 (2009)","journal-title":"ACM Transactions on Algorithms"},{"issue":"5","key":"22_CR22","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.H.M., DasGupta, B.: The rectangle enclosure and point-dominance problems revisited. International Journal of Computational Geometry and Applications 7(5), 437\u2013455 (1997)","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"22_CR23","unstructured":"Kaplan, H., Mulzer, W., Roditty, L., Seiferth, P.: Spanners and reachability oracles for directed transmission graphs. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 34 (2015)"},{"key":"22_CR24","doi-asserted-by":"crossref","unstructured":"Kaplan, H., Mulzer, W., Roditty, L., Seiferth, P., Sharir, M.: Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2495\u20132504 (2017)","DOI":"10.1137\/1.9781611974782.165"},{"issue":"6","key":"22_CR25","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0925-7721(96)00027-2","volume":"8","author":"MJ Katz","year":"1997","unstructured":"Katz, M.J.: 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects. Computational Geometry 8(6), 299\u2013316 (1997)","journal-title":"Computational Geometry"},{"issue":"3","key":"22_CR26","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jcss.1995.1078","volume":"51","author":"R Seidel","year":"1995","unstructured":"Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. Journal of Computer and System Sciences 51(3), 400\u2013403 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR27","doi-asserted-by":"crossref","unstructured":"Snoeyink, J.: Point location. In: Handbook of Discrete and Computational Geometry, 2nd edn., pp. 767\u2013785. CRC Press (2004)","DOI":"10.1201\/9781420035315.pt4"},{"key":"22_CR28","doi-asserted-by":"crossref","unstructured":"Williams, V.V.: Multiplying matrices faster than Coppersmith-Winograd. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pp. 887\u2013898 (2012)","DOI":"10.1145\/2213977.2214056"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-62127-2_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T16:17:06Z","timestamp":1709828226000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-62127-2_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319621265","9783319621272"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-62127-2_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"5 July 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"St. John's","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 August 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.wads.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}