Blockers for triangulations of a convex polygon and a geometric maker-breaker game

Let G be a complete convex geometric graph whose vertex set P forms a convex polygon C, and let F be a family of subgraphs of G. A blocker for F is a set of diagonals of C, of smallest possible size, that contains a common edge with every element of F. Previous works determined the blockers for various families F of non-crossing subgraphs, including the families of all perfect matchings, all spanning trees, all Hamiltonian paths, etc. In this paper we present a complete characterization of the family B of blockers for the family T of triangulations of C. In particular, we show that |B| = F_2n−8, where F_k is the k’th element in the Fibonacci sequence and n = |P |. We use our characterization to obtain a tight result on a geometric Maker-Breaker game in which the board is the set of diagonals of a convex n-gon C and Maker seeks to occupy a triangulation of C. We show that in the (1: 1) triangulation game, Maker can ensure a win within n − 3 moves, and that in the (1: 2) triangulation game, Breaker can ensure a win within n − 3 moves. In particular, the threshold bias for the game is 2.