In this paper, we present a new algorithm for fast online motion segmentation with low time complexity. Feature points in each input frame of an image stream are represented as a spatial neighbor graph. Then, the affinities for each point pair on the graph, as edge weights, are computed through our effective motion analysis based on multi-temporal intervals. Finally, these points are optimally segmented by agglomerative hierarchical clustering combined with normalized modularity maximization. Through experiments on publicly available datasets, we show that the proposed method operates in real time with almost linear time complexity, producing segmentation results comparable with those of recent state-of-the-art methods.