Finding closest line segment intersecting rays

Question

Assuming we have a fixed set of line segments $S$ such that any two segments are either disjoint or have a common endpoint.

A query would look like this; given a query point $q$ shoot 4 rays from $q$ (both sides horizontally and both sides vertically) and report the line segment in $S$ closest to $q$ intersecting any on these rays.

Is there a way to do this faster than $O(n)$ by preprocessing the data and storing it in some data structure? Or do we have to check for intersections with all segments for each ray and then compute the distances from the intersected line segments to $q$?

• D.W.: en.wikipedia.org/wiki/Sweep_line_algorithm, en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm

Answer 1

You'll need two data structures - for vertical rays and for horizontal rays. I'll describe a data structure for vertical rays. Draw a vertical line through each segment end - you'll get a set of vertical slabs. Each of these slabs will be divided by pieces of original segments into trapezoids (possibly infinite ones).

SlabsForThreeSegments

Number of these slabs will not exceed 2ドルn$, and number of trapezoids in each slab will not exceed $n$. In order to find a segment, closest to the query point along a vertical ray (going up or down), you need to use binary search to find a slab at first, and then - another binary search to find a trapezoid inside the found slab. Upper and lower boundary of this trapezoid will give you the answer. These two binary searches will take $O(log(n))$ time.

The data structure for horizontal rays is similar - the only difference is that slabs should be horizontal.