Abstract. Robust model fitting plays a vital role in computer vision,
and research into algorithms for robust fitting continues to be active. Arguably the most popular paradigm for robust fitting in computer vision
is consensus maximisation, which strives to find the model parameters
that maximise the number of inliers. Despite the significant developments in algorithms for consensus maximisation, there has been a lack
of fundamental analysis of the problem in the computer vision literature.
In particular, whether consensus maximisation is “tractable” remains a
question that has not been rigorously dealt with, thus making it difficult
to assess and compare the performance of proposed algorithms, relative
to what is theoretically achievable. To shed light on these issues, we
present several computational hardness results for consensus maximisation. Our results underline the fundamental intractability of the problem,
and resolve several ambiguities existing in the literature.