2
$\begingroup$

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.

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ I do not know if this helps, but: Associate to a point $(k,l)$ the line $kx+ly+1=0$ (this does not work for $(0,0)$...). They partition the plane into regions. Your questions are then equivalent to 1: determine if two given points lie in the same region, 2: enumerate all the regions. $\endgroup$ – Ivan Izmestiev Aug 29 '19 at 14:12
4
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Max, thanks for your answer. I'm glad that people have already thought about this kind of thing. Correct me if I'm wrong, but the solution that you're suggesting is this: Given a line $l$ as above, we can determine a threshold function $g$. The essential points of $g$ form the unique minimal teaching set for $g$. That teaching set always consists of 3 or 4 grid points. Assuming that I haven't already misunderstood something, can you tell me how to actually compute a teaching set from $l$? $\endgroup$ – sitiposit Sep 2 '19 at 1:37
  • $\begingroup$ In your paper referenced above, I noticed two examples, 7x +5y ≤55 and 3x +2y ≤22, of threshold functions with the corresponding minimal teaching sets: (3,7), (5,4), (8,0) and (0,8),(1,7),(6,2),(7,1) respectively. Can you explain how to compute these minimal sets? $\endgroup$ – sitiposit Sep 2 '19 at 14:29
  • $\begingroup$ @sitiposit: I don't have an algorithm handy, so please refer to the literature. Alternatively, one can try to find an integral point in "between" of two lines. This was the problem reduces to counting the integral points in the polyhedrons defined by the lines and boundaries, which is well studied. It should be relatively easy on the plane. $\endgroup$ – Max Alekseyev Sep 3 '19 at 16:57
1
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Ivan, Bresenham's algorithm is O(max(n,m)) (isn't it?). I was hoping for a more efficient way to determine the equivalence class of an arbitrary line ... I think i can arrange for O(log n), but I'm hoping for a O(1) computation. Is that too ambitious? $\endgroup$ – sitiposit Sep 2 '19 at 0:22
  • $\begingroup$ Hi Max, just to clarify, in order to compute anything for a given line you need to examine its data, such as the intercepts with the axes.. So my question is how precisely are you defining the line numerically? For example, are the intercepts rational numbers with bounded height? i.e. Note that any line that passes through any 2 points in the integer grid has intercepts with denominators bounded above by $n$. $\endgroup$ – Ivan Meir Sep 2 '19 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.