Defect location clustering schemes

Algorithms for clustering n objects typically require O(n²) operations. This report presents a special approach for a certain class of data that requires O(n) operations and O(n) storage. Such data commonly occur when a microscopic signal structure is imposed on a medium with potential for macroscopic defects, and the signal elements are then checked sequentially for error. The algorithm can be used to cluster other classes of data in O(n log n) operations. An application to videodisc defect consolidation is presented.