# Finding closest line segment intersecting rays

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. Mar 21 at 22:52

Number of these slabs will not exceed $$2n$$, 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.