Last Updated: 1 Oct, 2021
Garden Fencing
Hard
Asked in companies
Ninja owns a garden in the city of Ninjago. To prevent trespassers, he must fence the garden, but he is busy and asked you to help him.
You are given an array ‘Trees’ of size ‘N’ denoting the coordinates of each tree.
You want to impress Ninja by creating a circular fence such that all the trees lie either inside the fence or on the boundary of the fence. To minimize the cost you have to build the smallest possible fence. Find the coordinates of the centre and also find the radius of this circular fence.
Note :
Answers with a relative error of less than or equal to 10 ^ -5 are acceptable.
For Example :
If N = 3 and the trees are present at (0, 0), (1, 0) and (2, 0)
Then building a circle with (0, 0) and (2, 0) as diametric endpoints will result in the formation of the smallest circle enclosing all the trees.
Therefore we will return the centre as (1, 0) and radius equal to 1.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a single integer ‘N’ denoting the number of trees.
The next ‘N’ lines each contain two integers ‘X’ and ‘Y’ denoting the x-coordinate and y-coordinate of each tree.
Output Format :
For each test case, print the three values, the x-coordinate of the centre, the y-coordinate of the centre and the radius of the centre.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 ≤ T ≤ 10
1 ≤ N ≤ 5000
-10^9 ≤ X, Y ≤ 10^9
Time limit: 1 sec
Approaches
The problem involves geometrical observations that may seem too mathematical to you, and one may not expect this problem in a regular interview unless it is very math-heavy :D
There are few observations:
- The smallest circle passing through two distinct points has both points as diametric endpoints.
- A circle passing through three different points will always be unique, but this circle will be smallest only if all the three arcs formed subtend an angle less than 180 degrees, else the smallest circle enclosing all the three points will be formed by choosing two of these points as ends of the diameter.
There are few approaches that will give TLE but are worth discussing, we can consider all the pair-wise points as diametric endpoints and find if other remaining points are enclosed in it, we will also need to check for all the circles passing through three distinct points, and then for each circle, we will need to check if all the remaining points are enclosed in it or not. This will work because of the fact that a unique circle passes through three distinct points. But this approach is very time-consuming, in fact, it has a time complexity of O( (N2 * N) + (N3 * N) ) ~ O(N4).
Can we do better than this? The answer to this is YES!
We know that the smallest enclosing circle will surely pass through at least two points, you may think that how did we conclude that? Try marking some random points and draw the smallest enclosing circle, you will get a great intuition that the circle will always pass at least through two points.
Now simply consider two points, and try finding the smallest enclosing circle passing through these two points. Think of a way to solve this on your own first!
Still not able to figure out? Refer to the image below, centres of the circles passing through two given points will always line on a straight line and this straight line is the perpendicular bisector of the segment joining these two points, all these circles can be determined by varying the radius. In the image, the line marked in yellow is the perpendicular bisector and two different radius r1 and r2 are marked for your reference.
To find the smallest enclosing circle passing through two given points we can apply binary search on the radius of the circle, using math we can then find the centre for the circle and check if all the points are enclosed in the circle or not, if they are enclosed then we can try finding a smaller circle through binary-search. We can now simply extend this to all the pair-wise points and find the smallest enclosing circle amongst all, but the time complexity of this is still of order ~O( N3 * logX ), where X denotes the range of x-coordinates and y-coordinates. [ This approach also acts as proof for Observation 2, you may try proving it yourself ]
But this problem can be solved in linear time using Welzl's algorithm, you may find this a little confusing at first, but will surely admire the beauty of this algorithm later on.
If you know the Smallest Enclosing Circle (SEC) for i points, and now take an i+1’th point outside the SEC, then the SEC passing through all these i+1 points must also pass through the i+1’th point.
We will try proving this through the method of contradiction. Let the i+1’th point lie inside the SEC (refer to the figure below). Now for sure, there will be three points that will be the part of first i points that define the new SEC formed, but using the property of intersection of two circles we know that the intersected arc of the bigger circle will always be less than equal to half of its total circumference clearly depicted in this diagram, also the larger circle will be formed by the SEC of i+1 points because new SEC will be bigger than the old SEC to now include the i+1’th point. But this is completely wrong as the circle unique defined by the points A, B, C has the arc(A, C) subtending an angle greater than 180 degrees, and thus the SEC formed by considering points A,B and C should be formed by point A and point B as ends of the diameter. Therefore, we can conclude that the i+1’th point must lie on the SEC.
To solve this question, you must know how to directly calculate the coordinates of the centre and radius of the circle formed by three points. It can be challenging to come up with a method to calculate this accurately, so I'll use one of the methods available online.
Also, note that Welzl's algorithm involved randomly permuting the input, we can directly use the shuffle method to do this, if your language doesn’t support the shuffle method then you can even shuffle an array yourself using the Fisher–Yates shuffle Algorithm, the name may sound scary but this algorithm involves iterating the input array and swapping each element with an element at a random position.
The easiest way to implement the solution for this question is using recursion.
The steps are as follows :
- Randomly shuffle the input.
- Declare a container ‘boundaryPts’ to store the points lying on the boundary of the current smallest circle.
- Make the initial call for the function ‘SEC’ to calculate the smallest enclosing circle, pass N-1 as the initial parameter.
- In the ‘SEC’ function, parameter ‘i’ keeps the track of the current tree. Define the base condition to end recursion when we have either ‘i’ equals to -1 or when the size of ‘boundaryPts’ is equal to three.
- In the ‘SEC’ function, firstly make a recursive call to calculate the smallest circle formed by the first i-1 trees.
- Once we have calculated the smallest circle formed by i-1 trees, then check if the i’th tree lies inside the smallest circle or not, if it lies inside the circle we can return the recursive call to now calculate the smallest circle for the first i+1 trees, but incase the i’th point lies outside the circle then we will need to recalculate the SEC formed by first i trees with an additional condition that the i’th tree surely lies on the smallest circle.
- Finally, return the smallest circle enclosing all the ‘N’ trees.