{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:37:39Z","timestamp":1787319459675,"version":"3.56.0"},"reference-count":14,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[1988,2]]},"abstract":"<jats:p>A zero-sum game with a maximizer that selects a point x in given polygon R in the plane and a minimizer that selects K points $c_1 ,c_2 , \\cdots ,c_K $ in the plane is considered; the payoff is the Euclidean distance from x to the closest of the points $c_j $, or any monotonically nondecreasing function of this quantity. Lower and upper bounds on the value of the game are derived by considering, respectively, the maximizer\u2019s strategy of selecting a uniformly distributed random point in R and the minimizer\u2019s strategy of selecting K members of a (uniformly) randomly positioned grid of centers that induce a covering of R by K congruent regular hexagons. The analysis shows that these strategies are asymptotically optimal (for $K \\to \\infty $). For Euclidean location problems with uniformly distributed customers, the results imply that hexagonal partitioning of the region is asymptotically optimal and that the uniform distribution is asymptotically the worst possible.<\/jats:p>","DOI":"10.1137\/0401006","type":"journal-article","created":{"date-parts":[[2005,2,23]],"date-time":"2005-02-23T05:58:04Z","timestamp":1109138284000},"page":"50-64","source":"Crossref","is-referenced-by-count":15,"title":["Extremum Properties of Hexagonal Partitioning and the Uniform Distribution in Euclidean Location"],"prefix":"10.1137","volume":"1","author":[{"given":"M.","family":"Haimovich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"T. L.","family":"Magnanti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,8]]},"reference":[{"key":"RBS","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(72)90147-0"},{"key":"RF1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02024494"},{"key":"RF2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-01206-2"},{"key":"RHA1","unstructured":"M. Haimovich, On the asymptotic behavior of large random K-median Problems in the plane, 1979, unpublished notes"},{"key":"RHA2","unstructured":"M. Haimovich, Large scale geometric location problems I: deterministic limit properties, Working Paper, OR 130-85, Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA, 1985, January"},{"key":"RHA3","unstructured":"M. Haimovich, Large scale geometric location problems II: deterministic limit properties, Working Paper, OR 131-85, Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA, 1985, January"},{"key":"RHAM","unstructured":"M. Haimovich, T. L. Magnanti, Location games and bounds for median problems, Working Paper, OR 133-85, Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA, 1985, January"},{"key":"RHM","volume-title":"Location on networks theory and algorithms","author":"Handler G.","year":"1979"},{"key":"RI","doi-asserted-by":"publisher","DOI":"10.1007\/BF01897027"},{"key":"RKS","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584989"},{"key":"RPA","doi-asserted-by":"publisher","DOI":"10.1137\/0210040"},{"key":"RTH","doi-asserted-by":"publisher","DOI":"10.5962\/bhl.title.11332"},{"key":"RTH","doi-asserted-by":"publisher","DOI":"10.5962\/bhl.title.11332"},{"key":"RZ","doi-asserted-by":"publisher","DOI":"10.1137\/0606017"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0401006","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:48:49Z","timestamp":1787316529000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0401006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,2]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1988,2]]}},"alternative-id":["10.1137\/0401006"],"URL":"https:\/\/doi.org\/10.1137\/0401006","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,2]]}}}