On an interview I was asked to implement an algorithm that solves the mentioned problem. I initially got an idea of brute-force approach with O(n^2) time complexity, but I continued thinking about other approaches. And soon I discovered that it's simple to estimate vertical or horizontal lines only (I mean, with linear time complexity). But why?? Because it's possible to represent each line as a single number X or Y (and hence, use a dictionary), and it's easy to convert any point to such a line. And what prevents me from doing the same for other lines? Some slopes?.. So, let's fix it!
Thus I decided to rotate the coordinates looking for the longest horizontal line in the new coordinate system. In addition, this solution can easily deal with float numbers. And the time complexity is O(n*k) where k is a customizable constant. However, the pecision is not comolete, and usual execution time may be quite long because the k is a big number (for good precision).
Here is a brief explanation of the algorithm work:
But it also has a couple of constants, multiplication and rounding. For more details, look at alg_rot.py. It's interesting to note that this algorithm is even shorter than BF.
And here is the algorithms execution time comparison:
You can find table with comparison data here.
These software and algorithm is provided 'as-is', without any express or implied warranty. You may not hold the author liable. Permission is granted to anyone to use these software and algorithm for any purpose, including commercial applications, and to alter it and redistribute it freely, subject to the following restrictions: The origin of these software and algorithm must not be misrepresented. You must not claim that you wrote the original software or algorithm. When use the software or algorithm, you must give appropriate credit, provide an active link to the original file, and indicate if changes were made. This notice may not be removed or altered from any source distribution.