3

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.

Joe 2.0
  • 31
  • 2

2 Answers2

0

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.)
Parcly Taxel
  • 103,344
  • Thank you! This way we will find all points vertically below it, right? Would there be any optimization for instead simply checking if there is at least one point under the segment? I suppose returning true as soon as you find one would work, but I am interested in a more structural improvement. Thanks for your help! – Joe 2.0 Jan 08 '20 at 18:24
0

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.

Smokesick
  • 1
  • 1
  • I think using duality is probably the way to go! What do you mean when you say checking if the line is above the intersection point? I have played around with some examples in the link you sent and I found that if the point is vertically below the segment, it seems that its dual line won't enter the "triangle" under the wedge intersection point. Is that what you meant? – Joe 2.0 Jan 09 '20 at 16:08
  • "That its dual line won't enter the 'triangle' under the wedge intersection point." This is correct. Also, it might be a bit late now, but I hope you considered a traditional 2D Range Tree because that would also answer the question. You would have a query with two vertical sides be the $x$-coordinates of the endpoints of the line segment, and one horizontal side at the top of the query rectangle of the endpoint with largest $y$-coordinate. The bottom side is effectively unbounded and you can check all points in the range for intersection and perform early-out if you find a valid one. – Smokesick Jan 10 '20 at 00:14
  • I think this would be less efficient than Parcly's answer. Preprocessing the arrangement takes O(n2) time, then you'd have to insert the wedge which can take O(n) time, but then you might as well brute force without pre-processing. I think if the segment q is part of the arrangement, you might be able to obtain quick lookups because you won't have to insert lines anymore. Parcly's preprocessing is O(nlogn) and reduces lookup time to O(k) where k is the number of points in the x-coordinate range of the segment $q$. – none Jan 10 '20 at 15:26