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.

An example of the situation I described

  • 1
    $\begingroup$ And what is your question? Since you want to devise this algorithm, what do you have so far? $\endgroup$ – Evil Feb 22 '17 at 2:00
  • $\begingroup$ 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. $\endgroup$ – montagne Feb 22 '17 at 2:09
  • $\begingroup$ 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. $\endgroup$ – greybeard Feb 22 '17 at 7:51
  • $\begingroup$ 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. $\endgroup$ – Discrete lizard Feb 25 '17 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.