A tight lower bound on the size of visibility graphs (Q1098639)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A tight lower bound on the size of visibility graphs
scientific article

    Statements

    A tight lower bound on the size of visibility graphs (English)
    0 references
    1987
    0 references
    The visibility graph of a finite set of line segments in the plane connects two endpoints u and v if and only if the straight line connection between u and v does not cross any line segment of the set. The article proves that the visibility graph of n nonintersecting line segments has at least 5n-4 edges. This lower bound is tight. The result is of some interest in connection with the following problem: Is there an algorithm for constructing the visibility graph which takes less than \(\Omega\) (n 2) time if the number of edges of this graph is subquadratic?
    0 references
    computational geometry
    0 references
    combinatorial geometry
    0 references
    visibility graph
    0 references
    lower bound
    0 references
    0 references
    0 references

    Identifiers