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:


$such-that: X+Y=L$

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:


$such-that: X*Y>=P$



You're correct. We will place the points one at a time, in a zigzag greedy fashion, so that no lattice points are wasted. Redefine $n$ to be the number of points. Now for each $i\in \{1,...,n\}$, let $P_i$ be the $i$th point to be placed. Notice that since any integer $i$ lies between two consecutive perfect squares of the form $k^2$ and $k^2 + 2k + 1$ (where $k=\lfloor \sqrt{i} \rfloor$), we can uniquely express $i$ in the form $i=k^2+r$, where $r\in \{0,1,...,2k\}$. We now map each point to the Cartesian plane as follows:

$$ P_i = \begin{cases} (k,k) & \text{if } r = 0 \\ (k+1,r) & \text{if } r \in \{1,...,k\} \\ (r-k,k+1) & \text{if } r \in \{k+1,...,2k\} \\ \end{cases} $$

For example, since $14=3^2+5$ and $5\in \{4,5,6\}$, we would place the $14$th point $P_{14}$ at $(5-3,3+1)=(2,4)$.

Note that if $L(n)$ is the total number of drawn lines after placing down the $n$ points $P_1,P_2,...,P_n$, and if we express $n$ in the form $n=k^2+r$ where $r\in \{0,1,...,2k\}$ as above, then: $$ L(n) = \begin{cases} 2k & \text{if } r = 0 \\ 2k+1 & \text{if } r \in \{1,...,k\} \\ 2k+2 & \text{if } r \in \{k+1,...,2k\} \\ \end{cases} $$

  • $\begingroup$ This makes much sense, but, can you prove it is indeed optimal? $\endgroup$ – Erel Segal-Halevi May 30 '13 at 9:17
  • $\begingroup$ The AM-GM inequality shows this is correct. You need $mn \ge P$ with $m+n$ minimal. $\endgroup$ – Ross Millikan Jun 18 '13 at 4:13
  • $\begingroup$ Not sure I understand. The original minimization problem can be written as "Minimize the arithmetic mean, such that the geometric mean is at least $\sqrt p$". We know that the arithmetic mean is at least as large as the geometric mean, i.e., at least $\sqrt p$. How do we get from this to a solution to the original problem? $\endgroup$ – Erel Segal-Halevi Jun 21 '13 at 7:22

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.