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.
$O(n \log n)$ algorithm for disjoint segment visibility problem
algorithms;computational geometry
W.o.l.g. we could assume $P$ is the origin point $(0,0)$.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.  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)$.  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). 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.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)$.