On Bichromatic Triangle Game

Autor(es)

Manic, Gordana ; Martin, Daniel M. ; Stojakovic, Milos

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE APPLIED MATHEMATICS; v. 164, p. 6-pg., 2014-02-19.

Resumo

We study a combinatorial game called Bichromatic Triangle Game, defined as follows. Two players R and 2 construct a triangulation on a given planar point set V. Starting from no edges, they take turns drawing one straight edge that connects two points in V and does not cross any of the previously drawn edges. Player R uses color red and player 2 uses color blue. The first player who completes one empty monochromatic triangle is the winner. We show that each of the players can force a tie in the Bichromatic Triangle Game when the points of V are in convex position, and also in the case when there is exactly one inner point in the set V. As a consequence of those results, we obtain that the outcome of the Bichromatic Complete Triangulation Game (a modification of the Bichromatic Triangle Game) is also a tie for the same two cases regarding the set V. (C) 2012 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 08/06508-8 - Otimização discreta e grafos: algoritmos, teoria e aplicações
• Beneficiário: Gordana Manic
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores