Blocking visibility for points in general position (Q2391198): Difference between revisions

If \(P\) and \(Q\) are two disjoint sets of points in the plane, we say that \(p_1,p_2\in P\) see one another if there is no point of \(Q\) on the line segment connecting \(p_1\) and \(p_2\). If no pair of points in \(P\) sees one another, we call \(Q\) a visibility-blocking set for \(P\). The main problem treated in this lovely paper is estimation of the minimal size of visibility-blocking set for an \(n\)-point set \(P\) in general positioin. The paper contains the proofs of following results: 1) (Due to János Pach) There is an \(n\)-point set \(P\) in general position and a \(ne^{C\sqrt{\log n}}\)-point set \(Q\) such that \(Q\) is a visibility-blocking for \(P\). 2) For every \(n\)-point set \(P\) in general position any visibility-blocking set must have at least \(2n-3\) points. 3) For every \(n\)-point set \(P\) in convex position, any visibility-blocking set must have at least \(\Omega(n\log n)\) points. 4) There is a \(n\)-point set \(P\) in general position and a \(n\)-point set \(Q\), such that \(Q\) meets every line spanned by a pair of points in \(P\).