Abstract: Registration of point clouds is a fundamental problem in shape acquisition and shape modeling. In this paper, a novel technique, the sample-sphere method, is proposed to register a pair of point clouds in arbitrary initial positions. This method roughly aligns point clouds by matching pairs of triplets of points, which are approximately congruent under rigid transformation. For a given triplet of points, this method can find all its approximately congruent triplets in O(knlog n) time, where n is the number of points in the point cloud, and k is a constant depending only on a given tolerance to the rotation error. By employing the techniques of wide bases and largest common point set (LCP), our method is resilient to noise and outliers. Another contribution of this paper is proposing an adaptive distance restriction to improve ICP (iterative closest point) algorithm, which is a classical method to refine rough alignments. With this restriction, the improved ICP is able to reject unreasonable corresponding point pairs during each iteration, so it can precisely align the point clouds which have large non-overlapping regions.