[Solved]: $O(n \log n)$ algorithm for disjoint segment visibility problem

Problem Detail: 

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.

Asked By : VahidM

Answered By : Tianren Liu

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54302

3.2K people like this

 Download Related Notes/Documents