There are $P$ points in the 2-dimensional plane. Through each point, we draw two orthogonal lines: one horizontal (parallel to x axis), one vertical (parallel to y axis). Obviously, some of these lines conicide. How can we arrange the points such as the total number of lines is minimized?
I started with solving the dual problem (is that the correct name?): suppose we are allowed exactly $L$ lines, what is the maximum number of points we can have?
Suppose the number of different x values is $X$, and the number of different y values is $Y$. Then the number of lines is $L=X+Y$, and the maximum number of points is $P=X*Y$. So we have the following optimization problem:
AFAIK, the solution to this problem is to take X and Y as close as possible, e.g., if $L$ is even, take $X=Y=L/2$, and then $P=(L/2)^2$.
However, I don't know how to go from this to the original problem. For example, if we have $P=14$ points, then we can arrange them in a 7-by-2 grid and have $L=9$ lines, but we can also arrange them in a 4-by-4 grid with 2 points missing, then we will have only $L=8$ lines. So, how can I find the solution to the original minimization problem: