We present a novel scan matching algorithm, IDC-S, Iterative Dual Correspondence-Sector, that matches range scans. The algorithm is based on the known Iterative Dual Correspondence, IDC, algorithm which has shown good performance in real environments. The improvement is that IDC-S is able to deal with relatively large changes in the environment. It divides the scan in several sectors, detects and removes those sectors that are changed and matches the scans only using unchanged sectors. IDC-S and other variants of IDC are extensively simulated and evaluated. The simulations show that IDC-S is very robust and can locate in many different kind of environments. We also show that it is possible to effectively combine the existing IDC algorithms with IDC-S, thus obtaining an algorithm that performs very well both in rectilinear as well as nonrectilinear environments, even when changed as much as 65%. © 1999 IEEE.