Home » Subject » Geometry

Point sets with no empty pentagon

Importance: Low ✭
Author(s): Wood, David R.
Subject: Geometry
Keywords: combinatorial geometry
visibility graph
Recomm. for undergrads: yes
Posted by: David Wood
on: December 14th, 2010
Problem   Classify the point sets with no empty pentagon.

Let $ P $ be a finite set of points in the plane (not necessarily in general position). Two points $ x,y\in P $ are visible if the line segment $ xy $ contains no other point in $ P $. The visibility graph of $ P $ has vertex set $ P $, where two vertices are adjacent if and only if they are visible. An 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 empty pentagon (called a 5-hole),
$ B := $ point sets with no 5 pairwise visible points,
$ C := $ point sets whose visibility graph is 4-colourable.

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:

    \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?

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

Related problems

Big Line or Big Clique in Planar Point Sets

Bibliography

Z. Abel, B. Ballinger, P. Bose, S. Collette, V. Dujmovic, F. Hurtado, S. D. Kominers, S. Langerman, A. Pór, D. R. Wood. Every large point set contains many collinear points or an empty pentagon, Graphs and Combinatorics 27(1):47-60, 2011.

Eppstein, David. Happy endings for flip graphs. J. Computational Geometry 1(1):3-28, 2010. MathSciNet

Kára, Jan; Pór, Attila; Wood, David R. On the chromatic number of the visibility graph of a set of points in the plane. Discrete Comput. Geom. 34(3):497-506, 2005. MathSciNet

Pfender, Florian. Visibility graphs of point sets in the plane. Discrete Comput. Geom. 39 (2008), no. 1-3, 455–459. MathSciNet

Rabinowitz, Stanley. Consequences of the pentagon property. Geombinatorics 14:208-220, 2005.


* indicates original appearance(s) of problem.
add new comment

Problem 3 solved

On February 1st, 2014 David Wood says:

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

reply

Problem 2 solved

On March 25th, 2019 Leonard Nguyen ... says:

Since the chromatic number is always equal or greater than the clique number, the chromatic number of the visibility graph of sets in A is also unbounded.

Cibulka, Kyncl and Valtr have also indirectly solved problem 2.

reply

Comment viewing options

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