I have a set of lines (linear functions of the form y = mx + b) (120 of them!) and if I graph them all, then they partition the R^2 plane. The lines do not necessarily go through the origin.
What is the most efficient way to find all partitions created by a set of such lines? Personally, I'm having a hard time coming up with any way at all, let alone an efficient one. To be more clear, I include the following image of just 4 lines:
An example of a partition would be the set {(x,y)| -30x+28<= y && 60x+2 <= y <= 90x+7}
, which is the partition created by the red, yellow and green lines in the first quadrant. Another example would be {(x,y)|y <= -30x+28 && 5x+3 <= y <= 60x+2}
, which is the triangle in the first quadrant that is bounded by the blue, red and green lines.
An example of a non partition would be {(x,y)|5x+3 <= y <= -30x+28}
, which is the set bounded by the green line above and the blue line below. This is not a partition because there are several partitions contained within it (like the second set above, for instance), or overlapping it. The set {(x,y)|5x+3 <= y <= -30x+28 && 90x+7 <= y}
, however, would be a partition.
The desired output would be a complete list of such sets:
{(x,y)|y <= -30x+28 && 5x+3 <= y <= 60x+2},{(x,y)| -30x+28<= y && 60x+2 <= y <= 90x+7}...
etc. They don't have to be given in this notation, of course.
I'm not sure how to approach this problem, and so, unfortunately, can't provide much in the way of what I have tried. Ideally, I would like to do this in R, Python, Mathematica or MATLAB, but I'm open to any option at this point.
EDIT: Since there seems to be an issue with notation, I'll clarify a bit. It is sufficient to simply get a list of conditions on points, such that all points meeting that condition would exactly define a partition. For example, a long list of intersections, would be fine: y <= 5x+3 && y >= 90x+7 && y<= -30x+28
is perfectly good output defining a partition. The desired output, of course, is a complete list of such partitions (as defined above).
Definition 1.4. A plane partition is an array π = (πij)i,j≥1 of nonnegative integers such that π has finitely many nonzero entries and is weakly decreasing in rows and columns.
The number of region in which N non-parallel lines can divide a plane is equal to N*( N + 1 )/2 + 1.
The problem of finding the largest number of regions into which n straight lines can divide the (affine) plane is well known: the answer is n(n + 1)/2 + 1, achieved precisely when the n lines are “in general position,” that is, no two of them are parallel and no three concurrent.
Finding the number of partitions follows this formula (when no 3 or more lines intersect at the same point - this assumption is carried throughout this post):
num_partitions = (n_lines * (n_lines + 1) / 2 ) + 1
An explanation can be found here, and another one there.
The desired output would be a complete list of such sets:
{(x,y)|y <= -30x+28 && 5x+3 <= y <= 60x+2}, {(x,y)| -30x+28<= y && 60x+2 <= y <= 90x+7}...
etc... They don't have to be given in this notation, of course.
Below is my back of the envelop attempt. As you see, it is possible to identify the numbered areas based on their relative positioning to each line.
There are 5 empty sets, which won't be the same if the lines ordering changes.
It would probably be easier to partition a set of points on the plane with lines, trying to determine which point belongs to which set; in such a case, exploring the 2^n
potential partitions, and returning their content would be easy. (easier than trying to find a good notation for identifying an abstract set)
This doesn't fully answer your question, but may be a good strating point for someone able/willing to push this further.
Here is a note on partitioning a set of points with two lines in the plane.
it is a different problem, but some of its approach could be useful.
Identify the polygons formed by the line segments, calculate a convex hull, determine if a point is in that hull.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With