Consider a set of $n$ red lines and $m$ blue lines, suppose there are $nm$ distinct red-blue intersections.


What is the minimum number of lines $L\_1,L\_2,\dots, L\_n$ such that the union contains all $nm$ intersection points except for exactly one?


A trivial construction is to take $n-1$ red lines and $m-1$ blue lines. I have not been able to find any case in which there is something better.


This problem is migrated from math.se , no advances were made.


Could someone point me to a more general family of problems or theory of this type? 


Best Regards.



Covering all except one of the purple intersection points of $n$ red and $m$ blue lines efficiently
The very nice paper "Cayley-Bacharach theorems and conjectures" by David Eisenbud, Mark Green, and Joe Harris (<http://www.ams.org/journals/bull/1996-33-03/S0273-0979-96-00666-0/home.html>) gives an introduction to some related theory, including in particular a theorem which they number Theorem CB4: If $X\_1$ and $X\_2$ are two plane curves of degrees $d$ and $e$ meeting at $de$ distinct points, and if $C$ is any curve of degree $d+e-3$ containing all but one of the intersection points of $X\_1$ and $X\_2$, then $C$ contains all of the intersection points.


In particular, if any collection of $m+n-3$ lines covers $mn-1$ of the intersection points of the red and blue lines, then they have to cover all $mn$ intersection points (it's impossible to cover $mn-1$ and miss $1$, with $m+n-3$ or fewer lines). This shows that $m+n-2$ is the least number of lines that can cover $mn-1$ of the points and miss $1$.


Credit: I couldn't for the life of me dredge up the memory of "Cayley-Bacharach" until I read Douglas Zare's answer.


