Point sets with no empty pentagon

Importance: Low ✭
Author(s): Wood, David R.
Subject: Geometry
Recomm. for undergrads: yes
Posted by: David Wood
on: December 14th, 2010

\begin{problem} Classify the point sets with no empty pentagon. \end{problem}

Let $P$ be a finite set of points in the plane (not necessarily in general position). Two points $x,y\in P$ are \emph{visible} if the line segment $xy$ contains no other point in $P$. The \emph{visibility graph} of $P$ has vertex set $P$, where two vertices are adjacent if and only if they are visible. An \emph{empty pentagon} in $P$ consists of 5 points in $P$ that are the vertices of a strictly convex pentagon whose interior contains none of the points in $P$.

Consider the following three closely related classes of point sets:

$A :=$ point sets with no \Def[empty pentagon]{http://en.wikipedia.org/wiki/Happy_Ending_problem} (called a 5-hole),\\ $B :=$ point sets with no 5 pairwise visible points,\\ $C :=$ point sets whose visibility graph is 4-\Def[colourable]{http://en.wikipedia.org/wiki/Graph_coloring}.

By definition, $C \subseteq B \subseteq A$, and it is easy to show that $A \neq B$ and $B \neq C$.

A key example of a point set in $C$ is the planar grid (intersected with a convex set so that it is finite): colour each grid point $(x,y)$ by $(x \bmod 2, y \bmod 2)$. If $(x,y)$ and $(v,w)$ receive the same colour then $|x-v|$ and $|y-w|$ are both even, and thus the midpoint of $(x,y)$ and $(v,w)$ is a blocker. Hence the visibility graph of the grid is 4-colourable. [This result and proof is folklore.] Many other examples of point sets in these classes can be found in the references.

Consider the following open problems:

\begin{enumerate} \item Classify the point sets in $A$, $B$, or $C$\\ (i.e. list all examples; this is easy for point sets with no empty quadrilateral, or no 4 pairwise visible points).\\ \item Does the visibility graph of every point set in $A$ have bounded chromatic number?\\ \item Does the visibility graph of every point set in $A$ have bounded clique number?\\ \item Does the visibility graph of every point set in $B$ have bounded chromatic number? \end{enumerate}

Kára-Pór-Wood gave an example of a point set in $B$ with chromatic number $5$.


Z. Abel, B. Ballinger, P. Bose, S. Collette, V. Dujmovic, F. Hurtado, S. D. Kominers, S. Langerman, A. Pór, D. R. Wood. \href[Every large point set contains many collinear points or an empty pentagon]{http://dx.doi.org/10.1007/s00373-010-0957-2}, Graphs and Combinatorics 27(1):47-60, 2011.

Eppstein, David. \href[Happy endings for flip graphs]{http://jocg.org/index.php/jocg/article/view/21}. J. Computational Geometry 1(1):3-28, 2010. \MRhref{MR2469149}

Kára, Jan; Pór, Attila; Wood, David R. \href[On the chromatic number of the visibility graph of a set of points in the plane]{http://dx.doi.org/10.1007/s00454-005-1177-z}. Discrete Comput. Geom. 34(3):497-506, 2005. \MRhref{MR2160051}

Pfender, Florian. \href[Visibility graphs of point sets in the plane]{http://dx.doi.org/10.1007/s00454-008-9056-z}. Discrete Comput. Geom. 39 (2008), no. 1-3, 455–459. \MRhref{MR2383770}

Rabinowitz, Stanley. \href[Consequences of the pentagon property]{http://www.mathpropress.com/stan/bibliography/consequences.pdf}. Geombinatorics 14:208-220, 2005.

* indicates original appearance(s) of problem.

Problem 3 solved

Cibulka, Kyncl and Valtr have solved problem 3. They constructed point sets with no empty pentagon, and whose visibility graph has arbitrarily large clique number.

Josef Cibulka, Jan Kyncl and Pavel Valtr: On planar point sets with the pentagon property, Proc. SoCG 2013, pp. 81-90. http://dl.acm.org/citation.cfm?id=2462406

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.