0
$\begingroup$

Given $n$ points in $2$-dimensional plane, find a pair of points with the following properties:

  1. 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$.

  2. 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$.

  3. 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$

$\endgroup$
3
  • $\begingroup$ the distance from two points to the line will be same only if that line is perpendicular to line connecting both points $\endgroup$
    – Vasili
    Commented May 8, 2019 at 16:29
  • $\begingroup$ @Vasya that's not true. As long as the line to which we calculate distance will go through the middle point, the angle doesn't matter. That is because no matter the angle, the system of these two points and aline will have central symmetry in respect to the middle point. The perpendicular line has the property that its every point is in equal distance from the two original ponits. But the distance from the original points to the line don't have to be calculated to the same p[oint of the line. $\endgroup$
    – Adam Latosiński
    Commented May 8, 2019 at 16:36
  • $\begingroup$ #Vasya The distance does depend on the angle, yes, but if the line goes through the middle point then the distance of both original points from that line will be the same. The fact that those two distances are equal does not depend on the angle. $\endgroup$
    – Adam Latosiński
    Commented May 8, 2019 at 16:42

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Can the problem be solved without rotating and finding the new co-ordinates? When rotation comes into picture, I am not able to imagine anything :( $\endgroup$
    – Firex Firexo
    Commented May 8, 2019 at 16:44
  • $\begingroup$ You can do it without using labels $t_i$ and $s_i$, but it's functionaly the same. You order points once so that $x_1+y_1 \le \dots \le x_n + y_n$ and find $\min_i |(x_{i+1}+y_{i+1})-(x_i+y_i)|$, and then you order it again so that $y_1-x_1 \le \dots \le y_n-x_n$ and find $\min_i |(y_{i+1}-x_{i+1})-(y_i-x_i)|$. The smaller of these two results will give you the overall best pair of points. $\endgroup$
    – Adam Latosiński
    Commented May 8, 2019 at 16:52
  • $\begingroup$ Thankyou so much...I have a minor doubt, I think the solution only works if we conside the line of slope '-1', what if we consider the line of slope '-1', will have to do something else as well or this is the complete solution ?? $\endgroup$
    – Firex Firexo
    Commented May 8, 2019 at 17:54
  • $\begingroup$ this is the complete solution. These two orderings corresponds to the two possible slopes that need to be considered. If you'd only consider slope -1, it would be enough to consider $t_i$; if you only consider slope 1, then you'd only need to calculate $s_i$. $\endgroup$
    – Adam Latosiński
    Commented May 8, 2019 at 21:01
  • $\begingroup$ Thanks . This solution worked out for me, I've even derived the proof of your answer by co-ordinate geometry, will post it soon :-) $\endgroup$
    – Firex Firexo
    Commented May 9, 2019 at 5:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .