線分上の等距離点の最大数の計算

Question

直線セグメント上の点の集合を与えます。ポイントは、ライン上のどこにあってもよい。私は定期的な間隔でライン上にあるポイントの最大数を見つけるためにアキュロスを必要とします。

[3,0], [1,0], [4,0], [7,0],[11,0], [10,0] 

Output : 4 
    [1,0] , [4,0], [7,0], [10,0] 

例2：Y = 0で表される直線上

例えば、私のようないくつかの点有していてもよい

[2,1], [2,5], [2,3], [2,7], [2,6] 

Output: 4 
    [2,1], [2,3],[2,5], [2,7] 

を[注：行が任意の傾斜を有していてもよいです。私はアルゴリズムのスケッチだけが必要です。ポイントは2次元マトリックスに保存されていると考えられる場合があります] 助けてください。ここ

Answer 1

は擬似コードでブルートフォースアルゴリズムである：

for each point X 
    for each point Y != X 
    find number of connected points from X using the distance between X and Y 
    next Y 
next X 

XとYとの間の距離を使用してXから接続点の数を検索する方法：

dXY = Y - X 
i = 0 
while point_exists(X + i * dXY) 
    i = i + 1 
end while 

Answer 2

つ座標を選択しますゼロでない（またはより広い）範囲（たとえば、最初の例ではX）で、この座標でセットを並べ替えます。次に、最長算術の進展を見つけよう。