The one-round Voronoi game replayed. (English) Zbl 1068.65035
The authors resolve a number of problems raised by O. Cheong, S. Har-Peled, N. Linial and J. Matousek [The one-round Voronoi game, Discrete Comput. Geom. 31, 125–138 (2004; Zbl 1079.91010)]. A precise characterisation of the outcome of the game for optimal play is given. Furthermore, complexity aspects of the game are studied for a particular case.
Reviewer: Dana Petcu (Timişoara)
MSC:
| 91A05 | 2-person games |
| 91A46 | Combinatorial games |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 90B80 | Discrete location and assignment |
Keywords:
Voronoi game; optimal play; Voronoi diagram; game theory; computational geometry; competitive facility location; 2-person games; NP-hardnessCitations:
Zbl 1079.91010References:
| [1] | Ahn, H.-K.; Cheng, S.-W.; Cheong, O.; Golin, M.; van Oostrum, R., Competitive facility location: the Voronoi game, Theoret. Comput. Sci., 310, 457-467 (2004) · Zbl 1098.91003 |
| [2] | Cheong, O.; Efrat, A.; Har-Peled, S., On finding a guard that sees most and a shop that sells most, (Proceedings of the Fifteenth ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA (2004)), 1091-1100 · Zbl 1318.68181 |
| [3] | Cheong, O.; Har-Peled, S.; Linial, N.; Matousek, J., The one-round Voronoi game, Discrete Comput. Geom., 31, 125-138 (2004) · Zbl 1079.91010 |
| [4] | Dehne, F.; Klein, R.; Seidel, R., Maximizing a Voronoi region: the convex case, (Proceedings of the Thirteenth Annual International Symposium on Algorithms and Computation, vol. 2518 (2001)), 624-634 · Zbl 1019.68604 |
| [5] | Eiselt, H. A.; Laporte, G., Competitive spatial models, European J. Oper. Res., 39, 231-242 (1989) · Zbl 0661.90009 |
| [6] | Eiselt, H. A.; Laporte, G.; Thisse, J.-F., Competitive location models: a framework and bibliography, Transportation Sci., 27, 44-54 (1993) · Zbl 0767.90006 |
| [7] | Fekete, S. P.; Mitchell, J. S.B.; Weinbrecht, K., On the continuous Weber and \(k\)-median problems, (Proceedings of the Sixteenth Annual ACM Symposium on Computational Geometry (2000)), 70-79 · Zbl 1377.90054 |
| [8] | Fekete, S. P.; Meijer, H., The one-round Voronoi game replayed, (Proceedings 8th International Workshop on Algorithms and Data Structures. Proceedings 8th International Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, vol. 2748 (2003), Springer-Verlag: Springer-Verlag Berlin), 150-161 · Zbl 1192.91017 |
| [9] | Friesz, T. L.; Tobin, R. L.; Miller, T., Existence theory for spatially competitive network facility location models, Ann. Oper. Res., 18, 267-276 (1989) · Zbl 0707.90065 |
| [10] | Lichtenstein, D., Planar formulae and their uses, SIAM J. Comput., 11, 2, 329-343 (1982) · Zbl 0478.68043 |
| [11] | Lichtenstein, D.; Sipser, M., Go is polynomial-space hard, J. ACM, 27, 393-401 (1980) · Zbl 0434.68028 |
| [12] | Robson, J. M., The complexity of Go, (Information Processing: Proceedings of IFIP Congress (1983)), 413-417 |
| [13] | Rosenstiehl, P.; Tarjan, R. E., Rectilinear planar layouts and bipolar orientations of planar graphs, Discrete Comput. Geom., 1, 343-353 (1986) · Zbl 0607.05027 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
