Blocking visibility for points in general position (Q2391198): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00454-009-9185-z / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2044868365 / rank | |||
Normal rank |
Revision as of 02:15, 20 March 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