CODEWITHSUNDEEP
algorithmcomputational-geometryleast-squares
user9366862
user9366862

Reputation:

Given a two-dimensional graph with points, find a line that passes through the largest number of points

This problem comes from cracking the coding interview chapter 7 problem 6. To me as a mathematician this seems like a simple least squares problem where we find the best fit line. Although, in the solution they take a different approach.

My question is the following: is a developing a least squares approach a sufficient solution or am I not understanding the problem at hand?

Upvotes: 4

Views: 611

Answers (3)

Saumya Shah
Saumya Shah

Reputation: 36

Hough Transform is mostly what you are looking for. You may use Probabilistic version of it to speed up at the cost of some accuracy. OpenCv library has it implemented, but it isn't difficult to reimplement it.

Upvotes: 0

b9s
b9s

Reputation: 557

You can consider using the dual plane.
For any point p with coordinates p_x,p_y, you can convert it into its dual line p* = (y=p_xx-p_y).
For any line l: y=mx+b, you can convert it to its dual point l = (m, -b)

Colinear points in the plane then form intersecting lines in the dual plane. A line intersection algorithm can then be used to find the intersection point with the largest amount of lines. Translating this intersection point in the dual plane back to a line in the primal plane gives the line intersecting the largest amount of points.

See chapter 8.2 of Computation Geometry by M. de Berg et al for more specifics.

Upvotes: 0

user1196549
user1196549

Reputation:

Least squares isn't an appropriate solution, it doesn't care about the number of aligned points. The least-squares fit might contain no point at all.

The solution in the link by julian has an O(N²) behavior, assuming that a hash map has O(N) behavior to count duplicates. (With sorting, O(N²Log N) can be guaranteed.)

The main idea is to take every point in turn, to compute the directions to all other points, and count the coincident directions.

Upvotes: 2

Related Questions