Maximum mutually equidistant collinear points.

Revision en1, by oneandonly, 2017-04-21 08:13:13

Given a grid with R (Rows) and C (Coloumns) and N points (R,C) within the grid. I need to find the count of maximum mutually equidistant collinear points.

Mutually equidistant points here means, Every point on that line should be at equal distance with its neighbouring point on that line only (1,1 -> 3,3 -> 5,5 -> 7,7).

A line would be discarded if it contains non-mutually equidistant points(or point). (1-1 -> 3,3 ->5,5 -> 6,6-> 7,7 is an invalid line).

I came up with N^3 complexity approach, i.e consider any two points and check for every other point for collinearity and after each iteration , checking whether all the collinear points are mutually equi-distant or not. It's too slow to work. Is there any better approach?

Thank you.

Tags computational geometry, collinear

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English oneandonly 2017-04-21 08:13:13 801 Initial revision (published)