Carleton University
Technical Report TR-137
May 1988
An Efficient Computational Geometry Method for Detecting Dotted Lines in Noisy Images
Frank Dehne & L. Ficocelli
Abstract
In this paper we present an efficient O(n log n) time, linear space, algorithm for detecting a line, or lin e segment, represented by a set of nL collinear points contained in a rectangular window with an additional set of nN independant, uniformly distributed random noise points; n=nL +nN, Empirical results show that the algorithm is very reliable for nN/n 75%.