  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.
