# Nuts and Bolts problem: Simpler $o(n^2)$ algorithm

In this paper, the authors mention that it is possible to get an $o(n^2)$-time algorithm for the nuts and bolts problem by choosing samples based on a projective plane. They also mention that a non-constructive $O(n^{1.5}\log n)$-time algorithm can be obtained (pages 2-3). They omit the details.

I am interested in understanding these approaches, although they are not optimal. Could someone please provide the details of how this is done?

-
(1) Have you asked the authors? (2) It's not clear that these algorithms are "easy"! –  JɛﬀE Feb 11 '13 at 17:06
(1) Not yet. (2) I meant 'easier'..I've edited the question. –  Plummer Feb 12 '13 at 5:10