8
$\begingroup$

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?

Improve this question
$\endgroup$
  • 3
    $\begingroup$ (1) Have you asked the authors? (2) It's not clear that these algorithms are "easy"! $\endgroup$ – Jeffε Feb 11 '13 at 17:06
  • $\begingroup$ (1) Not yet. (2) I meant 'easier'..I've edited the question. $\endgroup$ – Plummer Feb 12 '13 at 5:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.