O(n3 logn) time complexity for the Optimal Consensus Set computation for Andres and

Abstract. This paper presents a method for fitting Andres circles as well as 4-connected digital circles to a given set of points in 2D images in the presence of noise by maximizing the number of inliers, namely the optimal consensus set, while fixing the thickness. Our approach based on one or several parameter spaces has a O(n3logn) time complexity, O(n) space complexity, n being the number of points, which is lower than previous known methods while still guaranteeing optimal solution(s)