enumerate line partitions of points in the plane Let $S$ be a nonempty subset of $\mathbb{R}^2$ and $l$ a line in $\mathbb{R}^2$ disjoint from $S$. Then $l$ partitions $S$ into two disjoint sets $S = S_1 \cup S_2$  in the obvious way. Note that, at least when $1 < |S| < \infty$, there are many lines that determine the same partition of $S$ as $l$ does.
Now let $m,n$ be positive integers and consider the case $S = \{0,1,2,\ldots,m\} \times \{0,1,2,\ldots,n\} \subset \mathbb{N}^2 \subset \mathbb{R}^2$.
Question 1: Given (the equations) of two lines how can I efficiently (i.e. without explicitly checking all the points in $S$) determine if these lines determine the same partition of $S$?
Question 2: How can I enumerate all such "line partitions" of $S$? Ideally, I should be able to efficiently determine the rank of an arbitrary line in this enumeration. 
 A: Such partitions are known under the name threshold functions. It is known that on a plane there exists a subset (teaching set) of $S$ of size 3 or 4 that completely defines the threshold function. Hence, the answer to the first question would be computing such a teaching set for one line and checking how the second line splits it. 
The second question is solved and exact formula is known (e.g. see OEIS A114043).
As a starting point I can suggest a paper of mine (which quotes related results and literature): 
On the minimal teaching sets of two-dimensional threshold functions.
A: I think you need to look at Bresenham's line algorithm. With this you can efficiently compute the integer points lying just under each curve and check they are the same. Clearly this means they determine the same partition.
Note also that the relation between two lines $l_1, l_2$ given by $l_1 \sim l_2$ if $l_1$ and $l_2$ determine the same partition is an equivalent relation.
For question 2 take a line with a specific gradient. Then you can rotate your grid so that the line is horizontal and sort the points by height. This gives you a set of horizontal bars lying between each of the points which define, for the particular gradient, lines that determine the same partition. Sampling over a reasonable number of gradients (by uniform angle $\theta$ if the gradient is $\tan \theta$) should given you a good sample.
If however you are interested in representatives of the equivalence class of lines then you need to classify this sample of lines into equivalence classes which shouldn't be too difficult using the answer to question 1.
Further thoughts: For question 1 for your two lines $l_1, l_2$ you could just find the points on the lines, $(i,y_{1i}),(i,y_{2i})$ for $i=0,\ldots,n$. If there is no integer point in the interval $(y_{1i},y_{2i})$ for any $i$ then the two lines define the same partition. Bresenham's algorithm allows you to compute this very efficiently but it's such a simple calculation it may not be worth bothering with.
