Computer Algorithms II Lecture Notes

2 October 2008 • Maximum Collinear Points

---

S is a set of integer points on a grid.

Lines through S may intersect points in S.

Find a largest subset of S through which a line can pass.

A point in S is either in a largest subset or not.

A point in the subset has a line passing through it. But which line?

Look at all lines through P.

For each line, count the other points it passes through.

Find the largest number of points intersected by any line through p.

unsigned max-intersects(p, S)
  mx = 0
  for p2 in S
    mx = max(mx, intersects(p, p2, S))
  return mx

unsigned intersects(p, p2, S)
  cnt = 0
  for p3 in S
    if collinear(p1, p2, p3)
      cnt++
  return cnt

Three points are collinear if any two pair have the same slope.

max-intersects() doesn't return the answer if p isn't in a subset.

Run max-intersects() over every point in S.

unsigned max-intersects(S)

  mx = 0

  for each p in S
    mx = max(mx, max-intersects(p, S))

  return mx

See the code.

intersects() is O(n); max_intersects() is O(n²).

unsigned intersects(p, p2, S)
  cnt = 2
  for p3 in S : O(n)
    if collinear(p1, p2, p3)
      cnt++
  return cnt

unsigned max-intersects(p, S)
  mx = 0
  for p2 in S : O(n)
    mx = max(mx,intersects(p,p2,S)) : O(n)
  return mx

max-intersects() is O(n³).

unsigned max-intersects(S)

  mx = 0

  for each p in S : O(n)
    mx = max(
      mx, max-intersects(p, S)) : O(n2)

  return mx

Compare each point with p once, not O(n) times.

All points collinear with p have the same slope.

Find all slopes with p; the most frequent one is the answer.

unsigned max_intersects(p, S)
  slopes = get-slopes(p, S)
  sort(slopes)
  return max-group-size(slopes)

A slope is a relatively-prime pair of numbers.

slope [] get-slopes(p, S)
  for p2 in S
    if p ≠ p2
      delta-x = p.x - p2.x
      delta-y = p.y - p2.y
      g = gcd(delta-x, delta-y)
      slopes.append(
        (delta-x/g, delta-y/g))

  return slopes

Order slopes as a fraction, or lexicographically.

bool < (slope s1, slope s2)
  return s1.x*s2.y < s1.y*s2.x

bool < (slope s1, slope s2)
  return 
    s1.x < s2.x ∨
    s1.x = s2.x ∧ s1.y < s2.y

Once grouped, find the most frequently occurring slope.

unsigned max-group-size(slopes)

  assert slopes.size > 0
				
  mx = 1
  group-start = 0

  for i = 1 to slopes.size - 1
    if slopes[i] ≠ slopes[group-start]
      mx = max(mx, i - group-start)
      group-start = i

  return mx

See the code.

get-slopes() is O(n).

slope [] get-slopes(p, S)
  for p2 in S : O(n)
    if p ≠ p2
      delta-x = p.x - p2.x
      delta-y = p.y - p2.y
      g = gcd(delta-x, delta-y) : O(?)
      slopes.append(
        (delta-x/g, delta-y/g))

  return slopes

max-group-size() is O(n).

unsigned max-group-size(slopes)

  mx = 1
  group-start = 0

  for i = 1 to slopes.size - 1 : O(n)
    if slopes[i] ≠ slopes[group-start]
      mx = max(mx, i - group-start)
      group-start = i;

  return mx

max-intersects() is O(n log n).

unsigned max-intersects(p, S)
  slopes = get-slopes(p, S) : O(n)
  sort(slopes) : O(n log n)
  return max-group-size(slopes) : O(n)

max-intersects() is O(n² log n).

unsigned max-intersects(S)

  mx = 0

  for each p in S : O(n)
    mx = max(mx, 
      max-intersects(p, S)) : O(n log n)

  return mx

So What?

Summary

• Find a maximum collinear subset in a point set.

• Dumb solution: look at all lines.

  • An O(n³) solution.

• Slightly less dumb solution: look at all slopes.

  • An O(n² log n) solution.

• Slightly less dumb wins.

Slopes should be grouped, but soring is expensive.

unsigned max_intersects(p, S)
  slopes = get-slopes(p, S)
  sort(slopes)
  return max-group-size(slopes)

Store slopes in a custom hash table.

hash-table get-slopes(p, S)

  hash-table slopes(|S|*3)

  for p2 in S
    delta-x = p.x - p2.x
    delta-y = p.y - p2.y
    g = gcd(delta-x, delta-y)
    slopes.add(delta-x/g, delta-y/g)

  return slopes

Once grouped, find the most frequently occurring slope.

unsigned max-group-size(slopes)

  mx = 0
  for i = 0 to slopes.size - 1
    if mx < slopes[i].size
      if slopes[i].collision
        mx = slope-max-count(slopes[i])
      else
	mx = slopes[i].size

  return mx

Collisions fall back to slope counting.

int slope-max-count(chain)
  max = 0
  while not chain.empty
    mx = 0
    for e = chain.head; e != nil
      if chain.head.slope == e.next.slope
        mx++
	chain.remove(e.next)
      else
        e = e.next
    max = max(mx, max)
  return max        

slope-max-count() is O(n²).

int slope-max-count(chain)
  max = 0
  while not chain.empty : O(n)
    mx = 0
    for e = chain.head; e != nil : O(n)
      if chain.head.slope == e.next.slope
        mx++
	chain.remove(e.next)
      else
        e = e.next
    max = max(mx, max)
  return max        

max-group-size() is O(n³).

unsigned max-group-size(slopes)

  mx = 0
  for i = 0 to slopes.size - 1 : O(n)
    if mx < slopes[i].size
      mx = if slopes[i].collision
        slope-max-count(slopes[i]) : O(n2)
      else
	slopes[i].size

  return mx

get-slopes() is O(n²).

hash-table get-slopes(p, S)

  hash-table slopes(|S|*3) : O(n)

  for p2 in S : O(n)
    deltax = p.x - p2.x
    deltay = p.y - p2.y
    g = gcd(deltax, deltay)
    slopes.add(deltax/g, deltay/g) : O(n)

  return slopes

max-intersects() is O(n³).

unsigned max_intersects(p, S)

  slopes = get-slopes(p, S) : O(n2)
  sort(slopes)
  return max-group-size(slopes) : O(n3)

max-intersects() is O(n⁴).

unsigned max-intersects(S)

  mx = 0

  for each p in S : O(n)
    mx = max(
      mx, 
      max-intersects(p, S)) : O(n3)

  return mx

See the code.

Well?

• Oh well.