How to tell if points in $Z^2$ belong to a half-plane?

Question

Suppose I have a list $(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$ of lattice vectors in the plane.

What is a good fast way to find another vector $(a,b)$ whose dot product with each $(x,y)$ is nonnegative, or else to prove that no such $(a,b)$ exists?

Answer 1

One could start by picking a vector pointing to one of the $(x_i,y_i)$ points. Take two copies of this. One will be used to search clockwise, and the other counterclockwise. Take the vector picked at the start as your initial "best guess" in each case. Going through the list of points, take a cross product $((x_1,y_1)\times(x_2,y_2)=x_1y_2-x_2y_1)$ of the point and the current best guess to figure out what side of the best guess the point is on. If it's farther clockwise, assign it as the new best guess. counter-clockwise for the opposite case. After you're done you'll have the two most extreme points (in the sense that rays shooting from the origin through these points define a region that contains all the other points). Now we just want to see if this region spans more than a 180 degree angle. This can be determined from the sign of their cross product. If positive, they span an angle of $<180^\circ$ and so normalizing them and taking their difference will give you the line you want. Otherwise, no such line exists.

This algorithm is linear in the number of points. You can't do any better (in the order of growth sense), since you need to check all the points at least once.