The way I am approaching this problem is to break the points in 2 d plane as 1 d points and finding the point with minimum maximum distance(Euclidean distance) to these points in x and y axis separately. For ex if points are {(2,3),(3,4),(5,6)} , I will take x coordinate (2,3,5) and find the point on x axis with minimum maximum distance to these points i.e. (2,3,5) and then take the y coordinate (3,4,6) and find the point on the y axis with minimum maximum distance to these points i.e. (3,4,6).My answer would be (x,y) obtained from this method. But it is giving wrong answer on some test case.
1
votes
If I understood the question correctly, I believe you should use euclidean distance i.e use pythagorean theorem to calciuate distances
– Amine Dakhli
Analysis of the specific test case that isn't working is your best bet. What were the points in it?
– paxdiablo
I am not able to see the test case and I am really confused how it should be wrong
– maria maria
If you want us to be able to help you, then you need to construct a minimal reproducible example. Please read the guidance on how to do that.
– Arya McCarthy
1 Answers
2
votes
The approach you're proposing is reasonable, but will not always work. Imagine, for example, that you're given these points: (0, -1), (0, +1), and (1, 0). The best place to put your point p would be at (0, 0) - do you see why? However, if you try to pick the x coordinate so that it minimizes the maximum distance to 0, 0, and 1, you'd pick x = 0.5, which is the wrong point. This means that you'll need to look for another solution route.
Suppose you have a collection of points in the 2D plane and decide to pick some point p as your answer. Let q be any of the points as far away from p as possible. Then if you were to draw a circle centered at p such that q was on the circumference of that circle, then all other points would have to be either inside the circle or on the perimeter of that circle. The point p that you're looking for would also have to minimize the radius of the circle drawn this way out of all the possible circles that could be drawn, since you're minimizing the maximum distance from p to any of the given points.
Given this, the problem you're trying to solve is equivalent to the following one: given a collection of points, what is the smallest circle that contains all of those points? Once you have the answer to that question, you can just pick the center of that circle as your point p. This problem is called the smallest circle problem and there are many fast algorithms for solving it.
