Blocking visibility for points in general position (Q2391198)

From MaRDI portal
Revision as of 01:00, 21 February 2024 by RedirectionBot (talk | contribs) (‎Removed claim: author (P16): Item:Q818688)
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
    0 references
    visibility
    0 references
    visibility-blocking set
    0 references
    Behrend's construction
    0 references

    Identifiers