Visibility and intersection problems in plane geometry (Q910213): Difference between revisions

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).