What is the most efficient algorithm to find a straight line that goes through most points?

by

There is likely no solution to this problem that is significantly better than O(n^2) in a standard model of computation.

The problem of finding three collinear points reduces to the problem of finding the line that goes through the most points, and finding three collinear points is 3SUM-hard, meaning that solving it in less than O(n^2) time would be a major theoretical result.

See the previous question on finding three collinear points.

For your reference (using the known proof), suppose we want to answer a 3SUM problem such as finding x, y, z in list X such that x + y + z = 0. If we had a fast algorithm for the collinear point problem, we could use that algorithm to solve the 3SUM problem as follows.

For each x in X, create the point (x, x^3) (for now we assume the elements of X are distinct). Next, check whether there exists three collinear points from among the created points.

To see that this works, note that if x + y + z = 0 then the slope of the line from x to y is

(y^3 – x^3) / (y – x) = y^2 + yx + x^2

and the slope of the line from x to z is

(z^3 – x^3) / (z – x) = z^2 + zx + x^2 = (-(x + y))^2 – (x + y)x + x^2
= x^2 + 2xy + y^2 – x^2 – xy + x^2 = y^2 + yx + x^2

Conversely, if the slope from x to y equals the slope from x to z then

y^2 + yx + x^2 = z^2 + zx + x^2,

which implies that

(y – z) (x + y + z) = 0,

so either y = z or z = -x – y as suffices to prove that the reduction is valid.

If there are duplicates in X, you first check whether x + 2y = 0 for any x and duplicate element y (in linear time using hashing or O(n lg n) time using sorting), and then remove the duplicates before reducing to the collinear point-finding problem.

More Related Contents:

  1. An algorithm for inflating/deflating (offsetting, buffering) polygons
  2. Sort points in clockwise order?
  3. How do I efficiently determine if a polygon is convex, non-convex or complex?
  4. What is the fastest algorithm to calculate the minimum distance between two sets of points?
  5. Largest circle inside a non-convex polygon
  6. How to check if line segment intersects a rectangle?
  7. How can I create an internal spiral for a polygon?
  8. Find if a point is inside a convex hull for a set of points without computing the hull itself
  9. Compute the area of intersection between a circle and a triangle?
  10. Location of highest density on a sphere
  11. How to determine if a point is in a 2D triangle? [closed]
  12. Circle line-segment collision detection algorithm?
  13. Algorithm to detect intersection of two rectangles?
  14. How do you calculate the average of a set of circular data? [closed]
  15. How to Compute OBB of Multiple Curves?
  16. How to compare two shapes?
  17. Combined area of overlapping circles
  18. Geo Fencing – point inside/outside polygon
  19. Calculate largest inscribed rectangle in a rotated rectangle
  20. What is the fastest way to find the closest point to a given point?
  21. Circle-circle intersection points
  22. Find the set of largest contiguous rectangles to cover multiple areas [duplicate]
  23. Sort Four Points in Clockwise Order
  24. How to find convex hull in a 3 dimensional space
  25. Circular approximation of polygon (or its part)
  26. Calculating the position of points in a circle
  27. Best way to find a point on a circle closest to a given point
  28. What is the algorithm for finding the center of a circle from three points?
  29. Algorithm for reflecting a point across a line
  30. How can I perform Collision Detection on rotated rectangles? [closed]

Leave a Comment