Blocking visibility for points in general position (Q2391198): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 19:58, 2 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Blocking visibility for points in general position |
scientific article |
Statements
Blocking visibility for points in general position (English)
0 references
24 July 2009
0 references
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\).
0 references
visibility
0 references
visibility-blocking set
0 references
Behrend's construction
0 references