7
$\begingroup$

Consider we have $n$ disjoint segments and a point $P$ which is not on any segment. I want to find an $O(n \log n)$ algorithm to check which segments are visible from $P$. A segment is visible from $P$ if it has a point which is visible from $P$.

My idea is to use a sweep half-line with one end-point on $P$, sort points clock-wise by degree and start from an end-point on the nearest visible segment (which I don't know how to find), rotate and detect one visible and some possible invisible segments at a time. All I can think of is $O(n^2)$ so far. Can anyone suggest an $O(n \log n)$ algorithm.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

W.o.l.g. we could assume $P$ is the origin point $(0,0)$.

  1. List the endpoints of all segments, represent them in polar coordinate $(\theta,\rho) \in [0,2\pi) \times [0,\infty)$ and sort them by their degree.
  2. Imagine there is an ray from $P$ pointing to the right, we sweep it for one round (by gradually changing its direction $\alpha$ from 0 to $2\pi$). Let $R(\alpha)$ denotes the ray from $P$ to direction $\alpha$. We wonder what's the segments $R(\alpha)$ hits, and what's their order on $R(\alpha)$.
  3. Find out all segments hit $R(0)$, and sort them by their order on $R(0)$. Store them in a balanced binary search tree (e.g. red-black tree).
  4. Iterate over the points we found (and sorted) in step 1: Each point $(\theta,\rho)$ indicates a segment would start/stop hitting the ray $R(\alpha)$ when $\alpha$ increase to $\theta$. Update the binary search tree accordingly.
  5. The elements that once be the smallest one in the binary search tree are the segments visible from $P$.

It's easy to check that the runtime of above algorithm is $O(n \log n)$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the solution. I have a doubt about 3rd and 4th step. How do we manage iterating over all points and checking intersection with $R(\alpha)$'s in $O(n \log n)$ ? $\endgroup$
    – VahidM
    Commented Mar 13, 2016 at 9:30
  • $\begingroup$ For 3rd step, you can enumerate are segments to check whether they hit $R(0)$, (this takes $O(n)$ time); the sort them by their intersection points on $R(0)$, (this takes $O(n \log n)$ time). $\endgroup$
    – Tianren Liu
    Commented Mar 14, 2016 at 0:03
  • $\begingroup$ @VahidM For the 4th step. We don't iterate over all points to find out who intersects with $R(\alpha)$. E.g. assume $(\theta,\rho)$ is one endpoint of a segment. Informally, we let $\theta_+$ ($\theta_-$) denotes a degree that is slightly larger (smaller) than $\theta$. Then we know the segments $R(\theta_+)$ intersects with are almost the same as the segments $R(\theta_-)$ intersects with. They differ only the segment related to $(\theta,\rho)$. So we know the set of segments hit $R(\theta_-)$, we could modify it in $O(\log n)$ time so that it becomes the set of segments hit $R(\theta_+)$. $\endgroup$
    – Tianren Liu
    Commented Mar 14, 2016 at 0:20
1
$\begingroup$

We can do a radial line sweep to solve the problem -

Sort the end points of the line segments w.r.t. the angle the line joining $P$ and the endpoint $Q$ make, break ties w.r.t. distance from $P$. Now when we sweep radially (in the clockwise direction) maintain two types of events 'open' and 'close' which correspond to opening and closing some new line segment. Keep track of how many line segments are 'active' at any given time ('active' means that we have encountered the end point which corresponds to the 'open' event of the line segment but we haven't encountered the other endpoint in the sweep yet). If at any point of time we have exactly one 'active' line segment, then this segment is visible from $P$.

We should be careful that when we start the sweep, we should always start at some 'open' event.

There will be $2n$ such events and keeping track of the number of active segments can be done in constant time per segment (via a hash table or logarithmuc time by using a balanced BST). Hence the dominating step in then algorithm is sorting which takes $\mathcal{O}(n)$ time as required.

As with all computational geometry problems, there might be some corner cases that I have overlooked but the general idea that if at some point of time during the radial line sweep, if we have exactly one active line segment, then it is visible from $P$ is the crux to solve this problem.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.