2010/02/01 by Greg Aloupis, Brad Ballinger, Sébastien Collette +3 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Optimization and Packing Problems #math.CO #msc:05D10 #msc:52C10
paper · pdf · doi:10.1007/978-1-4614-0110-0_4
published as In Thirty Essays on Geometric Graph Theory (János Pach, ed.), 31-48, Springer, 2012
arxiv created 2010/02/01 · crossref issued 2012/10/29 · crossref published 2012/10/29 · crossref published-online 2012/10/29 · openalex publication_date 2012/10/29 · crossref created 2012/12/13 · crossref published-print 2013/01/01 · arxiv updated 2015/11/17 · crossref deposited 2019/05/09 · openalex created_date 2019/06/27 · crossref indexed 2025/12/30 · openalex updated_date 2026/08/04
This paper studies problems related to visibility among points in the plane. A point x blocks two points v and w if x is in the interior of the line segment vw. A set of points P is k-blocked if each point in P is assigned one of k colours, such that distinct points v,w∈ P are assigned the same colour if and only if some other point in P blocks v and w. The focus of this paper is the conjecture that each k-blocked set has bounded size (as a function of k). Results in the literature imply that every 2-blocked set has at most 3 points, and every 3-blocked set has at most 6 points. We prove that every 4-blocked set has at most 12 points, and that this bound is tight. In fact, we characterise all sets \n1,n2,n3,n4\ such that some 4-blocked set has exactly ni points in the i-th colour class. Amongst other results, for infinitely many values of k, we construct k-blocked sets with k1.79... points.