We have an infinitely planar cartesian coordinate system on which $N$ points are plotted. Cartesian coordinates of the point $i$ are represented by $(X_i,Y_i)$. Now we want to draw $(N−1)$ line segments which may have arbitrary lengths and the points may or may not lie on these lines. The slope of each line must be $1$ or $−1$.

Let's denote the minimum distance we have to walk from a point $i$ to reach a line by $D_i$ and let's say $a=\max(D_1,D_2,D_3,...,D_N)$. We want this distance to be minimum as possible.

Thus we have to plot lines in such a way that it minimizes $a$ and compute $a \sqrt2$.

Devise an optimal procedure to find $a$ and thus compute $a \sqrt2$.

My understanding is as the slopes are $1$ or $-1$ the equations of the lines would be $y = x + c$ or $y = -x + c$ and we just have to find the y-intercept $c$ which minimizes the distance 'a' in the problem. Also, the minimum distance from a point to the line is the length of the perpendicular to the line. So I am having difficulty to devise an algorithm which will check all possible values of $'c'$ and find the optimal one.

  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – dkaeae May 10 '19 at 8:26
  • $\begingroup$ @dkaeae I've added my approach in the edit. If possible please help me solve it further. $\endgroup$ – user105099 May 10 '19 at 10:40
  • $\begingroup$ If you were allowed to draw $N$ line segments, could you solve this? $\endgroup$ – D.W. May 10 '19 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy