The superlinear blocking conjecture for general-position planar point sets

For a finite set PP of points in the plane, a set BB of points disjoint from PP blocks PP if every segment joining two distinct points of PP contains a point of BB. If PP is in general position, let b(P)b(P) be the minimum size of a blocking set for PP, and let b(n)b(n) be the minimum of b(P)b(P) over all nn-point sets in general position. Superlinear blocking conjecture. The minimum blocking number satisfies

b(n)nas n.\frac{b(n)}{n}\rightarrow\infty\quad\text{as }n\rightarrow\infty.

This asserts that every general-position point set requires superlinearly many blockers; Pinchasi conjectured the stronger bound b(n)Ω(nlogn)b(n)\in\Omega(n\log n).

Sources & referencesView supporting material

Primary source

Attila Pór and David R. Wood, “On Visibility and Blockers”, arXiv:0912.1150 (2009).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.