Data structure to check if there are any points under query line segment

Question

Let P be a set of points, where no three points are colinear and no two points have the same x- or y-coordinates. What is a good way of preprocessing P so that one can easily do queries in the below form: Given a line segment q, are there any points of P vertically below q? If a point is not within the x-range of q, we do not consider it to be "below" q.

Answer 1

Sort $P$ by increasing $x$-coordinate. Then, when a line segment is given by its two endpoints $a$ and $b$, where $a$ has a lower $x$-coordinate, we do the following:

1. Remove from consideration all points not under the segment. Since the points were sorted, this is just two binary searches and array lookup.
2. For each point $p$ that remains test whether it lies under the line segment. This may be done most efficiently by a cross product computation: $p$ is under iff $(p-a)×(b-a)>0$. (All letters refer to position vectors in this answer.)

Answer 2

I am considering point-line duality and have been experimenting with the following tool: https://people.eng.unimelb.edu.au/henli/programs/duality-demo/

In the dual plane, $q$ forms a wedge while point $p$ is a line.

You can observe that if $p$ is not in the $x$-range of $q$, then its line (in dual form) spans the (negative) top and bottom sides of the wedge of $q$. If the point is vertically above or below the line segment, the line spans (positive) left and right sides of the wedge.

Ensuring that the point is strictly below the line segment is a matter of checking that the line is above the intersection point of the two lines forming the wedge in the dual plane.

I think the data structure in question would be an arrangement of lines.

P.S. I would have commented but my reputation is too low to do so on this StackExchange. I would like to hear what others think.