# An interesting plane sweep algorithm?

I'd like to devise an algorithm which, given n non-intersecting line segments in the plane and a point p that does not lie on any of these segments, determines the region of the plane that is “visible” to p (see the image I've provided below). Ideally, this algorithm should run in O(n log n) time.

• And what is your question? Since you want to devise this algorithm, what do you have so far? – Evil Feb 22 '17 at 2:00
• Essentially, my question is this: How would I do this? I've thought about some sort of radial sweep process in the clockwise direction. It would account for whether or not a point has been "seen" by the sweep. For example, it could see if a segment is "open", and if the sweep finds an "open" segment, it would consider this segment to be visible. – montagne Feb 22 '17 at 2:09
• Aren't sweeps commonly used for set problems rather than query type problems? In a plane, for a set of non-intersecting segments $S$ and a set of points $P$ determine the "visible region" for all points $p$ from $P$. radial sweep I hear transformation (to a polar system around $p$). With non-intersecting line segments, pick any distance from each segment. – greybeard Feb 22 '17 at 7:51
• Transforming the points to polar coordinates is a bit overkill. Indeed, a 'radial sweep' is the right approach. However, you should determine which segments are visible from $p$, not all the points. Once you have determined the segments, it is simple to find the other boundaries of the visible region. – Discrete lizard Feb 25 '17 at 18:25