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

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: On the chromatic number of some geometric type Kneser graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: A statistical theorem of set addition / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Sets of Integers Which Contain No Three Terms in Arithmetical Progression / rank
 
Normal rank
Property / cites work
 
Property / cites work: Midpoints of Diagonals of Convex <i>n</i>-Gons / rank
 
Normal rank
Property / cites work
 
Property / cites work: The grid revisited / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the chromatic number of the visibility graph of a set of points in the plane / rank
 
Normal rank
Property / cites work
 
Property / cites work: Covering and coloring polygon-circle graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4400991 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4455112 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the number of directions determined by a three-dimensional points set / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Number of Intersection Points Made by the Diagonals of a Regular Polygon / rank
 
Normal rank

Latest revision as of 19:32, 1 July 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
    0 references
    visibility
    0 references
    visibility-blocking set
    0 references
    Behrend's construction
    0 references
    0 references

    Identifiers