Given N points, Draw N-1 lines with slope -1 or 1 such that the largest distance to any point is minimum. Hence find the largest distance.

Question

I am trying to solve following optimisation problem. Given N 2D points in format (x,y). We need to draw N-1 lines with slope either 1 or -1 , such that the maximum distance to any point is minimised.

I understand that in case when any two or more points lie on a line with slope -1 or 1 answer will be 0 as all points can lie on one of the lines. However when there no two points are on any line with slope -1 or 1, what will be the solution.

MY SOLUTION: find the half of minimum distance between parallel lines passing through points with slopes -1 or 1.

Reasoning: draw N-2 lines on points with farthest pairs except the last one and then draw N-1'th line between closest pair.

However i came to know this is not optimal solution. Please help.

Answer 1

The following algorithm will produce a set of lines with slope $+1$ or $-1$ with the shortest maximum distance. I assume the given points have coordinates $(x_n,y_n)$ for $n=1,2,\ldots,N$. Maybe go to the explanation of the general idea of the algorithm first, if you have triouble understanding what's going on.

1. Calculate $s_n=x_n+y_n$ for $n=1,2,\ldots,N$.
2. Order the resulting $s_n$ values from lowest to highest, keeping track of which point produced each value. This results in $N$ ordered values $s'_n$.
3. Find an index $k$ such that $s'_{k+1}-s'_k$ is the minimum of all $s'_{n+1}-s'_n$ over $n=1,2,\ldots,N-1$.
4. Find the indices $a$ and $b$ with $s_a=s'_k, s_b=s'_{k+1}$.
5. Calculate $d_n=x_n-y_n$ for $n=1,2,\ldots,N$.
6. Repeat steps 2-4, but use $d_n,d'_n$ instead if $s_n,s'_n$. This produces indices $e$ and $f$ instead of $a$ and $b$ in step 4 above.

The points $a$ and $b$ are the best candidates for 2 points that need to be 'covered' by one line of slope $-1$. If $s_a=s_b$, those points actually are on the same such line. If $s_a \neq s_b$, they were chosen such that the line with slope $-1$ through $(\frac{x_a+x_b}2, \frac{y_a+y_b}2)$ is the optimal line with slope $-1$ that covers any 2 points from the set with minmal maximal distance.

The same is true for points $e$ and $f$ with respect to lines with slope $+1$. They are the best pair of points to be covered by one line of slope $+1$, through point $(\frac{x_e+x_f}2, \frac{y_e+y_f}2)$.

To find out if to use a line of slope $+1$ or $-1$ to cover 2 different points, use the one that corresponds to the minumum of $|s_a-s_b|$ and $|d_e-d_f|$. If the minimum is $|s_a-s_b|$, use the line through $(\frac{x_a+x_b}2, \frac{y_a+y_b}2)$ with slope $-1$ to 'cover' points $a$ and $b$. If the minimum is $|d_e-d_f|$, use the line through $(\frac{x_e+x_f}2, \frac{y_e+y_f}2)$ with slope $+1$ to 'cover' points $e$ and $f$. If $|s_a-s_b|=|d_e-d_f|$, either variant works.

Now use your remaning $N-2$ lines to cover the remaining $N-2$ points (by going through them).

---

The idea of the algorithm is that you need 1 line to 'cover' 2 different points. A line 'covers' a point if it is one with the smallest distance to that point. Then all the other points can be easily covered by lines going through them. Because there are only 2 possible slopes, we try to find the optimal one for each direction (steps 1-4; 5-6).

Lines with slope $-1$ are characterized by the fact that for each point $(x,y)$ on them, the value $x+y$ is constant and describes the line. The euclidean distance between a point $(u,v)$ and the line $x+y=s$ ($s$ being a constant) is

$$\frac{|(u+v)-s|}{\sqrt 2}$$

Because ${\sqrt 2}$ is a constant, we can ignore it when comparing those distances. In step 1 we calculate that sum value $s_n$ for each line of slope $-1$ going through point $n$. By ordering them in step 2, we find wich of those lines are near each other, and we find the smallest distance in step 3. Step 4 then translates those 2 points back into our original naming scheme.

Then we do the same for lines with slope $+1$, which are characterized by $x-y=d$, $d$ being constant. So we calculate the differences $d_n$ in step 5, and then repeat steps 2-4 accordingly, as described in step 6.

At the end we then have to find out which slope of the two has the best (minimal) maximal distance.

Answer 2

1) The first step is to rotate the set of points by $\frac{\pi}{4}$

2) Sort in increasing order the points by the first coordinate forming the set $s_1$

3) Sort in increasing order the points by the second coordinate forming the set $s_2$

4) Calculate the differences $\Delta s_1=s_1(k+1)-s_1(k)$ and $\Delta s_2 =s_2(k+1)-s_2(k)$

5) Take the minimum of them. If $\min \Delta s_1 < \min\Delta s_2$ then choose a horizontal line passing just a half distance of those nearer and put a line passing across each of the remaining. If otherwise, draw a vertical line just equidistant of the nearest and draw a line across the remaining.