Xavier Holt edited Line_Moving_Queries_We_represent__.md  about 8 years ago

Commit id: b05d92a60dd44b29c6d5cfb2e776d912ae3629e4

deletions | additions      

       

# Line-Moving Queries  We represent the problem in the dual-plane. We find that by this representation our task is to find the closest  line \(s^*\)furthest  below our query point \(l^*\). We solve can find  thisproblem  by first finding all \(O(n^2)\) intersections constructing the arrangement  of our lines. We then finding lines \(S^*\) in  the convex hull dual-plane, and then building a trapezoidal-decomposition on top  of these intersections \(O(n^2 \log n)\) time, \(O(n^2)\) space. this. This allows us to find the face that any point we query resides in in \(O(\log n\)\).  We then perform a vertical line-query from \(l^*\) and find the bottom-most intersection point. point with the convex face.  We can map this back to the line \(\in S*\) that we're after. ## Dual Problem