Range sensing technology allows the photo-realistic modeling of large-scale scenes, such as urban structures. A major bottleneck in the process of 3D scene acquisition is the automated registration of a large number of geometrically complex 3D range scans in a common frame of reference. The generated 3D representations, after automated registration, are useful for urban planning, historical preservation, or virtual reality applications. Man-made urban scenes provide an abundance of linear features that can be used for the solution of the problem. Many scenes though require the utilization of non-linear primitives. This paper provides a solution of the registration problem based on the robust detection and matching of circular features from the range data sets. We present results from experiments with complex range scans from the interior of a large-scale landmark urban structure (Grand Central Terminal, NYC), where traditional methods would fail. This work is part of a larger range registration system that is based on extracted features of multiple geometric types.