A new upper bound for the VC-dimension of visibility regions

In this paper we are proving the following fact. Let P be an arbitrary simple polygon, and let S be an arbitrary set of 15 points inside P. Then there exists a subset T of S   that is not “visually discernible”, that is, T≠vis(v)∩ST≠vis(v)∩S holds for the visibility regions vis(v)vis(v) of all points v in P. In other words, the VC-dimension d of visibility regions in a simple polygon cannot exceed 14. Since Valtr [15] proved in 1998 that d∈[6,23]d∈[6,23] holds, no progress has been made on this bound. By ϵ-net theorems our reduction immediately implies a smaller upper bound to the number of guards needed to cover P.