{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T09:49:14Z","timestamp":1778233754847,"version":"3.51.4"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2022,12,5]],"date-time":"2022-12-05T00:00:00Z","timestamp":1670198400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,5]],"date-time":"2022-12-05T00:00:00Z","timestamp":1670198400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["FE407\/21-1"],"award-info":[{"award-number":["FE407\/21-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study competitive location problems in a continuous setting, in which facilities have to be placed in a rectangular domain <jats:italic>R<\/jats:italic> of normalized dimensions of 1 and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\rho \\ge 1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03c1<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and distances are measured according to the Manhattan metric. We show that the family of <jats:italic>balanced<\/jats:italic> facility configurations (in which the Voronoi cells of individual facilities are equalized with respect to a number of geometric properties) is considerably richer in this metric than for Euclidean distances. Our main result considers the <jats:italic>One-Round Voronoi Game<\/jats:italic> with Manhattan distances, in which first player White and then player Black each place <jats:italic>n<\/jats:italic> points in <jats:italic>R<\/jats:italic>; each player scores the area for which one of its facilities is closer than the facilities of the opponent. We give a tight characterization: White has a winning strategy if and only if <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\rho \\ge n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03c1<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>; for all other cases, we present a winning strategy for Black.\n<\/jats:p>","DOI":"10.1007\/s10479-022-04976-x","type":"journal-article","created":{"date-parts":[[2022,12,5]],"date-time":"2022-12-05T11:03:08Z","timestamp":1670238188000},"page":"79-101","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Competitive location problems: balanced facility location and the One-Round Manhattan Voronoi Game"],"prefix":"10.1007","volume":"321","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0548-4086","authenticated-orcid":false,"given":"Thomas","family":"Byrne","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9062-4241","authenticated-orcid":false,"given":"S\u00e1ndor P.","family":"Fekete","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5013-3448","authenticated-orcid":false,"given":"J\u00f6rg","family":"Kalcsics","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3786-916X","authenticated-orcid":false,"given":"Linda","family":"Kleist","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,12,5]]},"reference":[{"key":"4976_CR1","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2003.09.004","volume":"310","author":"H-K Ahn","year":"2004","unstructured":"Ahn, H.-K., Cheng, S.-W., Cheong, O., Golin, M., & van Oostrum, R. (2004). Competitive facility location: The Voronoi game. Theoretical Computer Science, 310, 357\u2013372. https:\/\/doi.org\/10.1016\/j.tcs.2003.09.004","journal-title":"Theoretical Computer Science"},{"key":"4976_CR2","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/0166-0462(93)90006-Z","volume":"23","author":"M Aoyagi","year":"1993","unstructured":"Aoyagi, M., & Okabe, A. (1993). Spatial competition of firms in a two-dimensional bounded market. Regional Science and Urban Economics, 23, 259\u2013289. https:\/\/doi.org\/10.1016\/0166-0462(93)90006-Z","journal-title":"Regional Science and Urban Economics"},{"issue":"2","key":"4976_CR3","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1287\/opre.2015.1354","volume":"62","author":"I Averbakh","year":"2015","unstructured":"Averbakh, I., Berman, O., Kalcsics, J., & Krass, D. (2015). Structural properties of Voronoi diagrams in facility location problems with continuous demand. Operations Research, 62(2), 394\u2013411. https:\/\/doi.org\/10.1287\/opre.2015.1354","journal-title":"Operations Research"},{"issue":"5","key":"4976_CR4","doi-asserted-by":"publisher","first-page":"879","DOI":"10.1080\/09672567.2019.1626460","volume":"26","author":"NE Aydinonat","year":"2019","unstructured":"Aydinonat, N. E., & K\u00f6ksal, E. (2019). Explanatory value in context: The curious case of Hotelling\u2019s location model. The European Journal of the History of Economic Thought, 26(5), 879\u2013910. https:\/\/doi.org\/10.1080\/09672567.2019.1626460","journal-title":"The European Journal of the History of Economic Thought"},{"key":"4976_CR5","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/j.tcs.2014.10.003","volume":"562","author":"S Bandyapadhyay","year":"2015","unstructured":"Bandyapadhyay, S., Banik, A., Das, S., & Sarkar, H. (2015). Voronoi game on graphs. Theoretical Computer Science, 562, 270\u2013282. https:\/\/doi.org\/10.1016\/j.tcs.2014.10.003","journal-title":"Theoretical Computer Science"},{"key":"4976_CR6","unstructured":"Banik, A., Bhattacharya, B. B., Das, S., & Mukherjee, S. (2013). One-round discrete Voronoi game in $$\\mathbb{R}^2$$ in presence of existing facilities. In Canadian conference in computational geometry (CCCG). https:\/\/www.cccg.ca\/proceedings\/2013\/papers\/paper_32.pdf"},{"key":"4976_CR7","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1016\/j.ejor.2006.10.023","volume":"183","author":"O Baron","year":"2007","unstructured":"Baron, O., Berman, O., Krass, D., & Wang, Q. (2007). The equitable location problem on the plane. European Journal of Operational Research, 183, 578\u2013590. https:\/\/doi.org\/10.1016\/j.ejor.2006.10.023","journal-title":"European Journal of Operational Research"},{"key":"4976_CR8","doi-asserted-by":"publisher","unstructured":"Bender, C. M., Bender, M. A., Demaine, E. D., & Fekete, S. P. (2004). What is the optimal shape of a city? Journal of Physics A: Mathematical and General, 37(1). https:\/\/doi.org\/10.1088\/0305-4470\/37\/1\/010","DOI":"10.1088\/0305-4470\/37\/1\/010"},{"issue":"4","key":"4976_CR9","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1016\/S0305-0548(02)00024-2","volume":"30","author":"J Bhadury","year":"2003","unstructured":"Bhadury, J., Eiselt, H. A., & Jaramillo, J. H. (2003). An alternating heuristic for medianoid and centroid problems in the plane. Computers & Operations Research, 30(4), 553\u2013565. https:\/\/doi.org\/10.1016\/S0305-0548(02)00024-2","journal-title":"Computers & Operations Research"},{"key":"4976_CR10","doi-asserted-by":"publisher","unstructured":"Byrne, T., Fekete, S. P., Kalcsics, J., & Kleist, L. (2021). Competitive location problems: Balanced facility location and the One-Round Manhattan Voronoi Game. In Workshop on algorithms and computation (WALCOM), LNCS (Vol. 12635, pp. 103\u2013115). https:\/\/doi.org\/10.1007\/978-3-030-68211-8_9","DOI":"10.1007\/978-3-030-68211-8_9"},{"issue":"1","key":"4976_CR11","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s00454-003-2951-4","volume":"31","author":"O Cheong","year":"2004","unstructured":"Cheong, O., Har-Peled, S., Linial, N., & Matou\u0161ek, J. (2004). The One-Round Voronoi Game. Discrete and Computional Geometry, 31(1), 125\u2013138. https:\/\/doi.org\/10.1007\/s00454-003-2951-4","journal-title":"Discrete and Computional Geometry"},{"key":"4976_CR12","doi-asserted-by":"publisher","unstructured":"Dasci, A. (2011). Conditional location problems on networks and in the plane. In Foundations of location analysis. International series in operations research & management science (Vol. 155, pp. 391\u2013429). https:\/\/doi.org\/10.1007\/978-1-4419-7572-0_9","DOI":"10.1007\/978-1-4419-7572-0_9"},{"issue":"5","key":"4976_CR13","doi-asserted-by":"publisher","first-page":"1145","DOI":"10.2307\/1911955","volume":"47","author":"C d\u2019Aspremont","year":"1979","unstructured":"d\u2019Aspremont, C., Gabszewicz, J. J., & Thisse, J.-F. (1979). On Hotelling\u2019s \u2018stability in competition\u2019. Econometrica, 47(5), 1145\u20131150. https:\/\/doi.org\/10.2307\/1911955","journal-title":"Econometrica"},{"key":"4976_CR14","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/0166-0462(82)90003-5","volume":"12","author":"Z Drezner","year":"1982","unstructured":"Drezner, Z. (1982). Competitive location strategies for two facilities. Regional Science and Urban Economics, 12, 485\u2013493. https:\/\/doi.org\/10.1016\/0166-0462(82)90003-5","journal-title":"Regional Science and Urban Economics"},{"key":"4976_CR15","doi-asserted-by":"crossref","unstructured":"Drezner, Z. (Ed.). (1995). Facility location: A survey of applications and methods. Springer.","DOI":"10.1007\/978-1-4612-5355-6"},{"key":"4976_CR16","doi-asserted-by":"crossref","unstructured":"Drezner, Z., & Hamacher, H. W. (Eds.). (2002). Facility location: Applications and theory. Springer.","DOI":"10.1007\/978-3-642-56082-8"},{"key":"4976_CR17","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.ejor.2008.01.022","volume":"195","author":"Z Drezner","year":"2009","unstructured":"Drezner, Z., & Suzuki, A. (2009). The minimum equitable radius location problem with continuous demand. European Journal of Operational Research, 195, 17\u201330.","journal-title":"European Journal of Operational Research"},{"key":"4976_CR18","doi-asserted-by":"publisher","unstructured":"D\u00fcrr, C. & Thang, N. K. (2007). Nash equilibria in Voronoi games on graphs. In European symposium on algorithms (ESA) (pp. 17\u201328). https:\/\/doi.org\/10.1007\/978-3-540-75520-3_4","DOI":"10.1007\/978-3-540-75520-3_4"},{"key":"4976_CR19","doi-asserted-by":"publisher","unstructured":"Eiselt, H. A., Marianov, V., & Drezner, T. (2019). Competitive location models. In L. Gilbert, N. Stefan, & F. Saldanha da Gama (Eds.), Location science (pp. 391\u2013429). Springer. https:\/\/doi.org\/10.1007\/978-3-030-32177-2_14","DOI":"10.1007\/978-3-030-32177-2_14"},{"issue":"3","key":"4976_CR20","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/j.tcs.2002.12.001","volume":"313","author":"SP Fekete","year":"2004","unstructured":"Fekete, S. P., Fleischer, R., Fraenkel, A. S., & Schmitt, M. (2004). Traveling salesmen in the presence of competition. Theoretical Computer Science, 313(3), 377\u2013392. https:\/\/doi.org\/10.1016\/j.tcs.2002.12.001","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"4976_CR21","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.comgeo.2004.05.005","volume":"30","author":"SP Fekete","year":"2005","unstructured":"Fekete, S. P., & Meijer, H. (2005). The One-Round Voronoi Game replayed. Computational Geometry, 30(2), 81\u201394. https:\/\/doi.org\/10.1016\/j.comgeo.2004.05.005","journal-title":"Computational Geometry"},{"key":"4976_CR22","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1287\/opre.1040.0137","volume":"53","author":"SP Fekete","year":"2005","unstructured":"Fekete, S. P., Mitchell, J. S. B., & Beurer, K. (2005). On the continuous Fermat\u2013Weber problems. Operations Research, 53, 61\u201376. https:\/\/doi.org\/10.1287\/opre.1040.0137","journal-title":"Operations Research"},{"key":"4976_CR23","doi-asserted-by":"publisher","first-page":"439","DOI":"10.7155\/jgaa.00331","volume":"18","author":"D Gerbner","year":"2014","unstructured":"Gerbner, D., M\u00e9sz\u00e1ros, V., P\u00e1lv\u00f6lgyi, D., Pokrovskiy, A., & Rote, G. (2014). Advantage in the discrete Voronoi game. Journal of Graph Algorithms and Applications, 18, 439\u2013457. https:\/\/doi.org\/10.7155\/jgaa.00331","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"4976_CR24","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1287\/opre.12.3.450","volume":"12","author":"SL Hakimi","year":"1964","unstructured":"Hakimi, S. L. (1964). Optimal location of switching centers and the absolute centers and medians of a graph. Operations Research, 12, 450\u2013459. https:\/\/doi.org\/10.1287\/opre.12.3.450","journal-title":"Operations Research"},{"key":"4976_CR25","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0377-2217(83)90180-7","volume":"12","author":"SL Hakimi","year":"1983","unstructured":"Hakimi, S. L. (1983). On locating new facilities in a competitive environment. European Journal of Operational Research, 12, 29\u201335.","journal-title":"European Journal of Operational Research"},{"issue":"153","key":"4976_CR26","doi-asserted-by":"publisher","first-page":"41","DOI":"10.2307\/2224214","volume":"39","author":"H Hotelling","year":"1929","unstructured":"Hotelling, H. (1929). Stability in competition. The Economic Journal, 39(153), 41\u201357. https:\/\/doi.org\/10.2307\/2224214","journal-title":"The Economic Journal"},{"issue":"1","key":"4976_CR27","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0377-2217(93)E0239-T","volume":"80","author":"R Infante-Macias","year":"1995","unstructured":"Infante-Macias, R., & Mu\u00f1oz-Perez, J. (1995). Competitive location with rectilinear distances. European Journal of Operational Research, 80(1), 77\u201385. https:\/\/doi.org\/10.1016\/0377-2217(93)E0239-T","journal-title":"European Journal of Operational Research"},{"issue":"6","key":"4976_CR28","doi-asserted-by":"publisher","first-page":"1185","DOI":"10.1587\/transinf.E94.D.1185","volume":"94","author":"M Kiyomi","year":"2011","unstructured":"Kiyomi, M., Saitoh, T., & Uehara, R. (2011). Voronoi game on a path. IEICE Transactions on Information and Systems, 94(6), 1185\u20131189. https:\/\/doi.org\/10.1587\/transinf.E94.D.1185","journal-title":"IEICE Transactions on Information and Systems"},{"issue":"3","key":"4976_CR29","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1287\/opre.29.3.616","volume":"29","author":"A Kolen","year":"1981","unstructured":"Kolen, A. (1981). Equivalence between the direct search approach and the cut approach to the rectilinear distance location problem. Operations Research, 29(3), 616\u2013620. https:\/\/doi.org\/10.1287\/opre.29.3.616","journal-title":"Operations Research"},{"key":"4976_CR30","doi-asserted-by":"publisher","unstructured":"Kusakari, Y., & Nishizeki, T. (1997). An algorithm for finding a region with the minimum total $${L}_{1}$$-distance from prescribed terminals. In International symposium on algorithms and computation (ISAAC) (pp. 324\u2013333). Springer. https:\/\/doi.org\/10.1007\/3-540-63890-3_35","DOI":"10.1007\/3-540-63890-3_35"},{"key":"4976_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32177-2","volume-title":"Location science","author":"G Laporte","year":"2019","unstructured":"Laporte, G., Nickel, S., & Saldanha-da-Gama, F. (2019). Location science. Springer. https:\/\/doi.org\/10.1007\/978-3-030-32177-2"},{"key":"4976_CR32","unstructured":"Launhardt, C. F. (1900). The principles of location: The theory of the trace. Part I: The commercial trace (A. Bewley, Trans.). Lawrence Asylum Press."},{"key":"4976_CR33","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1287\/mnsc.11.2.213","volume":"11","author":"AS Manne","year":"1964","unstructured":"Manne, A. S. (1964). Plant location under economies of scale-decentralization and computation. Management Science, 11, 213\u2013235. https:\/\/doi.org\/10.1287\/mnsc.11.2.213","journal-title":"Management Science"},{"key":"4976_CR34","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/0094-1190(91)90006-S","volume":"29","author":"A Okabe","year":"1991","unstructured":"Okabe, A., & Aoyagi, M. (1991). Existence of equilibrium configurations of competitive firms on an infinite two-dimensional space. Journal of Urban Economics, 29, 349\u2013370. https:\/\/doi.org\/10.1016\/0094-1190(91)90006-S","journal-title":"Journal of Urban Economics"},{"issue":"8","key":"4976_CR35","doi-asserted-by":"publisher","first-page":"1067","DOI":"10.1068\/a191067","volume":"19","author":"A Okabe","year":"1987","unstructured":"Okabe, A., & Suzuki, A. (1987). Stability of spatial competition for a large number of firms on a bounded two-dimensional space. Environment and Planning A: Economy and Space, 19(8), 1067\u20131082. https:\/\/doi.org\/10.1068\/a191067","journal-title":"Environment and Planning A: Economy and Space"},{"key":"4976_CR36","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/BF00935665","volume":"11","author":"M Simaan","year":"1973","unstructured":"Simaan, M., & Cruz, J. B. (1973). On the Stackelberg strategy in nonzero-sum games. Journal of Optimization Theory and Applications, 11, 533\u2013555. https:\/\/doi.org\/10.1007\/BF00935665","journal-title":"Journal of Optimization Theory and Applications"},{"key":"4976_CR37","doi-asserted-by":"publisher","unstructured":"Teramoto, S., Demaine, E. D., & Uehara, R. (2006). Voronoi game on graphs and its complexity. In IEEE conference on computational intelligence and games (CIG) (pp. 265\u2013271). https:\/\/doi.org\/10.1109\/CIG.2006.311711","DOI":"10.1109\/CIG.2006.311711"},{"key":"4976_CR38","volume-title":"The theory of the market economy","author":"H von Stackelberg","year":"1952","unstructured":"von Stackelberg, H. (1952). The theory of the market economy. Oxford University Press."},{"key":"4976_CR39","unstructured":"Weber, A. (1929). Theory of the location of industries (C. J. Friedrich, Trans.). University of Chicago Press."},{"key":"4976_CR40","first-page":"5","volume":"1","author":"GO Wesolowsky","year":"1993","unstructured":"Wesolowsky, G. O. (1993). The Weber problem: History and perspective. Location Science, 1, 5\u201323.","journal-title":"Location Science"},{"key":"4976_CR41","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800180107","volume":"18","author":"GO Wesolowsky","year":"1971","unstructured":"Wesolowsky, G. O., & Love, R. F. (1971). Location of facilities with rectangular distances among point and area destinations. Naval Research Logistics, 18, 83\u201390. https:\/\/doi.org\/10.1002\/nav.3800180107","journal-title":"Naval Research Logistics"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-022-04976-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-022-04976-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-022-04976-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T19:12:44Z","timestamp":1674673964000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-022-04976-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,5]]},"references-count":41,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["4976"],"URL":"https:\/\/doi.org\/10.1007\/s10479-022-04976-x","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,12,5]]},"assertion":[{"value":"29 August 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 December 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}