Given $n$ points in $2$-dimensional plane, find a pair of points with the following properties:
Suppose the two points are $(x_1,y_1)$ and $(x_2,y_2)$. We find their
midpoint(s), say, $(x_3,y_3)$, and draw a line of slope $\pm 1$ on the
point $(x_3,y_3)$. Let's call this line $L$.By geometry, the distance of points $(x_1,y_1)$ and $(x_2,y_2)'$ from the line $L$ is the same. Let that distance be $x$.
We want to find pair of points with minimum distance of $x$.
It is a programming problem , but I want to know if it can be used solving mathematics. 🙂
Example : –
Say,the following 3 points :-
0 1
1 0
0 -1
The required pair is :- $([0,1],[1,0])$, for which $x= 0$
Best Answer
To make it easier to imagine, rotate the whole picture py $45^\circ$. Then you still consider midle point, but the lines considered has to be either vertical or horizontal.
Let $t_i$ and $s_i$ be coordinates of points in a rotated coordinate system. Up to a scale factor of $\frac{1}{\sqrt{2}}$ which can be omitted for an optimization problem, you have $$ t_i = x_i+y_i, \qquad s_i = y_i-x_i$$ In theese coordinates, you have $x_{ij} =\frac12\min\{|t_i-t_j|,|s_i-s_j|\}$ and you're looking for a pair of points for which it is minimal. You can do it by first finding a pair of point for which $|t_i-t_j|$ is minimal and another pair for which $|s_i-s_j|$ is minimal; then comparate the two and choose the better pair.
To find the minimal $|t_i-t_j|$, let us sort the points such that $t_1\le t_2\le\dots\le t_n$. It is obivious that the minimal $|t_i-t_j|$ will happen for some pair of subsequent points, meaning $$ \min_{ij} |t_i-t_j| = \min_i |t_{i+1}-t_i| $$ So you don't need to check every pair of points, only the points ordered one after another.
You do an analogously thing to find $\min_{ij} |s_i-s_j|$ (probably, you'll need to sort the points again).
As I've said before, you have then $x_{ij} = \min\{\min_{ij} |t_i-t_j|, \min_{ij} |s_i-s_j|\}$, and you just need to recall what were the points that gave you this minimal value.