<p>In <a href="http://www.cs.ucla.edu/~rafail/PUBLIC/17.pdf" rel="nofollow">this paper</a>, the authors mention that it is possible to get an $o(n^2)$-time algorithm for <a href="http://www.wisdom.weizmann.ac.il/~naor/PUZZLES/nuts_solution.html" rel="nofollow">the nuts and bolts problem</a> 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. </p>

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

CC BY-SA 3.0
2013-02-11T17:06:55.853Z
(1) Have you asked the authors?  (2) It's not clear that these algorithms are "easy"!
Jeffε
CC BY-SA 3.0
2013-02-12T05:10:35.843Z
(1) Not yet. (2) I meant 'easier'..I've edited the question.
Plummer
<ds.algorithms>
Nuts and Bolts problem: Simpler $o(n^2)$ algorithm
Plummer
# Nuts and Bolts problem: Simpler $o(n^2)$ algorithm

(Asked by: username_0 on 2013-02-11)

In [this paper](http://www.cs.ucla.edu/~rafail/PUBLIC/17.pdf), the authors mention that it is possible to get an $o(n^2)$-time algorithm for [the nuts and bolts problem](http://www.wisdom.weizmann.ac.il/~naor/PUZZLES/nuts_solution.html) 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?

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: (1) Have you asked the authors?  (2) It's not clear that these algorithms are "easy"!  
> **username_0**: (1) Not yet. (2) I meant 'easier'..I've edited the question.  

---

## 0 answers

