Visibility and intersection problems in plane geometry (Q910213)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Visibility and intersection problems in plane geometry
scientific article

    Statements

    Visibility and intersection problems in plane geometry (English)
    0 references
    0 references
    0 references
    0 references
    1989
    0 references
    Within the field of visibility and intersection problems, the authors are focussing on the following problem: ``Given a simple polygon P and a pair (q,u) consisting of a point q and a direction u, imagine that we follow the path of a straight-line ray r from q in the direction u. We wish to know the first intersection (if any) of r with the boundary of P... In posing this question we assume that P is fixed once and for all, so we are allowed to do preprocessing on it.'' New data structures are proposed for solving this problem in O(log n)-time with preprocessing which takes time O(n log n) and space O(n).
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    computational geometry
    0 references
    visibility problems
    0 references
    intersection problems
    0 references
    0 references