Continuous Yao Graphs

In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points $Ssubset mathbb{R}^2$ and an angle $0 < theta leq 2pi$, we define the continuous Yao graph $cY(theta)$ with vertex set $S$ and angle $theta$ as follows. Foreach $p,qin S$, we add an edge from $p$ to $q$ in $cY(theta)$ if there exists a cone with apex $p$ and aperture $theta$ such that $q$ is the closest point to $p$ inside this cone. We study the spanning ratio of $cY(theta)$ for different values of $theta$. Using a new algebraic technique, we show that $cY(theta)$ is a spanner when $theta leq 2pi /3$. We believe that this technique may be of independent interest. We also show that $cY(pi)$ is not a spanner, and that $cY(theta)$ may be disconnected for $theta > pi$.

Coloring and Guarding Arrangements

Given an arrangement of lines in the plane, what is the minimum number $c$ of colors required to color the lines so that no cell of the arrangement is monochromatic? In this paper we give bounds on the number c both for the above question, as well assome of its variations. We redefine these problems as geometric hypergraph coloring problems. If we define $Hlinecell$ as the hypergraph where vertices are lines and edges represent cells of the arrangement, the answer to the above question is equal to the chromatic number of this hypergraph. We prove that this chromatic number is between $Omega (log n / loglog n)$. and $O(sqrt{n})$. Similarly, we give bounds on the minimum size of a subset $S$ of the intersections of the lines in $mathcal{A}$ such that every cell is bounded by at least one of the vertices in $S$. This may be seen as a problem on guarding cells with vertices when the lines act as obstacles. The problem can also be defined as the minimum vertex cover problem in the hypergraph $Hvertexcell$, the vertices of which are the line intersections, and the hyperedges are vertices of a cell. Analogously, we consider the problem of touching the lines with a minimum subset of the cells of the arrangement, which we identify as the minimum vertex cover problem in the $Hcellzone$ hypergraph.

Every Large Point Set contains Many Collinear Points or an Empty Pentagon

We prove the following generalised empty pentagon theorem: for every integer $ell geq 2$, every sufficiently large set of points in the plane contains $ell$ collinear points or an empty pentagon. As an application, we settle the next open case of thebig line or big clique conjecture of Kara, Por, and Wood [emph{Discrete Comput. Geom.} 34(3):497--506, 2005].