# How to efficiently compute Theil-Sen estimator?

The Theil-Sen estimator is of interest to me, however when I implement it myself I end up with something that scales as O(n^2). According to wikipedia, it can be calculated exactly in O(n log(n)). Can someone point me toward an efficient implementation (python or mathematica would be best, Matlab or R would be tolerable) or otherwise explain in simple terms how the efficient versions work?

According to wikipedia, it can be calculated exactly in O(n log(n)).

Wikipedia points to no less than six papers detailing different deterministic or randomized algorithms with $O(n\log n)$ performance, right in the section where they mention the existence of such algorithms (as well as mentioning an even faster one under particular circumstances).

Deterministic:

Cole, Richard; Salowe, Jeffrey S.; Steiger, W. L.; Szemerédi, Endre (1989), An optimal-time algorithm for slope selection, SIAM Journal on Computing 18 (4): 792–810, doi:10.1137/0218055, MR 1004799.

Katz, Matthew J.; Sharir, Micha (1993), Optimal slope selection via expanders, Information Processing Letters 47 (3): 115–122, doi:10.1016/0020-0190(93)90234-Z, MR 1237287.

Brönnimann, Hervé; Chazelle, Bernard (1998), Optimal slope selection via cuttings, Computational Geometry Theory and Applications 10 (1): 23–29, doi:10.1016/S0925-7721(97)00025-4, MR 1614381.

$\$

Randomized:

Dillencourt, Michael B.; Mount, David M.; Netanyahu, Nathan S. (1992), A randomized algorithm for slope selection, International Journal of Computational Geometry & Applications 2 (1): 1–27, doi:10.1142/S0218195992000020, MR 1159839.

Matoušek, Jiří (1991), Randomized optimal algorithm for slope selection, Information Processing Letters 39 (4): 183–187, doi:10.1016/0020-0190(91)90177-J, MR 1130747.

Blunck, Henrik; Vahrenhold, Jan (2006), "In-place randomized slope selection", International Symposium on Algorithms and Complexity, Lecture Notes in Computer Science 3998, Berlin: Springer-Verlag, pp. 30–41, doi:10.1007/11758471_6, MR 2263136.

Which did you want?

• Yes, I do know how to notice when references are made. I'd like the one that can be explained HERE in relatively SIMPLE terms. Alternatively the one that has been implemented so that one can just use the code. – mdeceglie Oct 20 '14 at 13:10
• I do prefer a method that computes it exactly rather than something that gives a slightly different answer each time. – mdeceglie Oct 20 '14 at 13:27
• Why the downvote? – COOLSerdash Oct 20 '14 at 15:45
• Italian, you mistake the meaning of a "randomized algorithm": these are algorithms that randomize their input in order to avoid rare worst-case situations. They have $O(n\log(n))$ expected computation time--but they produce exact, correct, repeatable optimal solutions. The deterministic algorithms Glen_b cites here tend to be complicated, whereas some of the randomized algorithms are relatively simple. The initial commentary in the last paper (Henrik Blunck and Jan Vahrenhold) explains this and provides an overview of several of the algorithms. – whuber Oct 20 '14 at 16:14
• italianice -- None of the algorithms are very simple; the papers explaining them leave out quite a few details (as being obvious enough that an expert could fill in the omitted details); all those would need to be explained - I can't seeing even the simplest being covered in less than many, many thousands of words (likely tens of thousands, plus diagrams). As far as I can see, all involve computational geometry in some way. The randomized algorithms tend to be somewhat simpler, but that's not saying much. If you really need this, your best bet might be to look for an implementation. – Glen_b -Reinstate Monica Oct 21 '14 at 6:16