hash function for the "find the line that contains the maximum number of points in P"

Question

Here is the passage from the Elements of Programming Interviews book:

Let P be a set of n points in the plane. Each point has integer coordinates. Design an efficient algorithm for computing a line that contains the maximum number of points in P.

In the solution part the following is said:

 Every pair of distinct points defines a line. We can use a hash table
H to map lines to the set of points in P that lie on them.

And here is the hash function of the Line:

// Hash function for Line.
struct HashLine {
   size_t operator()(const Line& l) const {
       return hash <int >()(l.slope.first) ^ hash <int >()(l.slope.second) ^ hash <int >()(l.intercept.first) ^ hash <int >()(l.intercept.second);
}

And here is the declaration of slope and intercept:

 pair <int, int> get_canonical_fractional(int a, int b) {
    int gcd = GCD(abs(a), abs(b));
    a /= gcd, b /= gcd;
    return b < 0 ? make_pair(-a, -b) : make_pair(a, b);
 }

     // Line function of two points , a and b, and the equation is
     // y = x(b.y - a.y) / (b.x - a.x) + (b.x * a.y - a.x * b.y) / (b.x - a.x).
     struct Line {
     Line(const Point& a, const Point& b)
     : slope(a.x != b.x ? get_canonical_fractional(b.y - a.y, b.x - a.x) : make_pair(1, 0))
     , intercept(a.x != b.x ? get_canonical_fractional(b.x * a.y - a.x * b.y,  b.x - a.x) : make_pair(a.x, 1))
     {}

       ...
     // Store the numerator and denominator pair of slope unless the line is
     // parallel to y-axis that we store 1/0.  
     pair <int, int> slope;
     // Store the numerator and denominator pair of the y-intercept unless
     // the line is parallel to y-axis that we store the x-intercept.     
     pair <int, int> intercept;
};

But how do we know that if slope and intercept pair are unique, then their xor is still unique?

What exactly is meant by line? Would it be feasible to generate the convex hull polygon of the input, which would contain all of the points? Or does the question demand for an affine linear function in which the number of pairs from the input which which form a valid argument-value pair is maximized? — Codor
similar to this Given n points on a 2D plane, find the maximum number of points that lie on the same straight line — Spektre
Hush function? Is it the one that tells your object to shut up? I know nothing about it, but a hash function need not produce unique values. It just needs to produce different values for different inputs with acceptable probability. — n. 1.8e9-where's-my-share m.

Sandipan Dey Sandipan Dey · Accepted Answer · 2017-02-20T08:21:41

We can try the following simple algorithm:

Create a hash map to with key as a (slope, intercept) pair for a line and value as the number of lines having the same slope intercept.
For all pairs of points (O(n^2) pairs) compute the (slope, intercept) value and increment the corresponding key in the hashmap (in the worst case, it will consume O(n^2) memory but if there are many co-linear points then the average space complexity should be low).
Output the line i.e., the (slope, intercept) that has the highest count in the hashmap (for this you need to traverse the hasmap which in the worst case will contain O(n^2) entries).

hash function for the "find the line that contains the maximum number of points in P"

1 Answers