CMS/SMC
CanaDAM 2013
Memorial University of Newfoundland, June 10 - 13, 2013 www.cms.math.ca//2013
       

Visibility and Geometry
Chair: Suzanne Seager (Mount Saint Vincent University)
[PDF]

BETTE BULTENA, University of Victoria
Minimum Area Polyomino Venn Diagrams  [PDF] [SLIDES]

Minimum area polyVenn diagrams are Venn diagrams in which each of the $2^n$ intersection regions, in a diagram of $n$ polyominoes, consists of one unit square.

We construct minimum area polyVenn diagrams in bounding rectangles of size $2^r \times 2^c$. Our construction depends on two ``expansion" results. First, a polyVenn in a $2^2 \times 2^c$ rectangle can be expanded to produce another one that fits into a $2^2 \times 2^{c+3}$ bounding rectangle. Second, a minimum area polyVenn diagram in a $2^r \times 2^c$ rectangle can be expanded to produce another one that fits into a $2^{r+1} \times 2^{c+1}$ rectangle.

BILL KINNERSLEY, Ryerson University
How long does it take to catch a robber?  [PDF] [SLIDES]

In the classic ``Cops and Robber'' game, a team of cops attempts to capture a robber on a graph; the {\em cop number} is the minimum number of cops needed to guarantee a win. The cop number has been extensively studied. We consider a natural question that has received less attention: how long does it take the cops to win? When both teams play optimally, the length of the game is called the {\em capture time}. Surprisingly little is known about this parameter. In this talk, we show that the capture time of the $d$-dimensional hypercube is $\Theta(d \log d)$.

KHALEGH MAMAKANI, University of Victoria
Simple symmetric Venn diagrams with 11 and 13 curves  [PDF] [SLIDES]

A collection of $n$ closed curves in the plane, with no three curves intersecting at a common point, is called a simple $n$-Venn diagram if it divides the plane into $2^n$ regions where each region is inside the interior of a unique subset of the curves. A (rotational) symmetric Venn diagram is the one that is invariant under rotation, up to a relabeling of the curves. Here we introduce the first simple Venn diagrams with 11 and 13 curves discovered using a computer search restricted to a new property called crosscut symmetry which is related to dihedral symmetry.

SUZANNE SEAGER, Mount Saint Vincent University
Locating a Robber on a Caterpillar  [PDF] [SLIDES]

Consider the following game of a cop locating a robber on a connected graph. At each turn, the cop chooses a vertex of the graph to probe and receives the distance from the probe to the robber. If she can uniquely locate the robber after this probe, then she wins. Otherwise the robber may stay put or move to any vertex adjacent to his location other than the probe. The cop's goal is to minimize the number of probes required to locate the robber; the robber's goal is to avoid being located. We consider an optimal cop strategy for caterpillars.

HAMIDEH VOSOUGHPOUR, University of Waterloo
Cops and Robbers in a Polygon  [PDF] [SLIDES]

We study the cops and robbers game on the infinite visibility graph of points inside a simple polygon, which has an edge between two points iff they are visible to each other. We show that the cop has a simple winning strategy in this game. For finite graphs, being cop-win and having a dismantlable ordering are equivalent. We propose a dismantlable ordering of the infinite set of points of a polygon and show that the maximum number of moves the cop needs is bounded by the number of reflex vertices. This is joint work with Anna Lubiw.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society Memorial University of Newfoundland