Calamoneri, Tiziana, Finocchi, Irene, Italiano, Giuseppe F.
Slope selection, i.e. selecting the slope with rank k among all 􀀀n 2lines induced by a collection P of points, results in a widely used robust estimator for linefitting. In this paper, we demonstrate that it is possible to perform slope selection in expected O(n·log2 n) time using only constant extra space in addition to the space needed for representing the input.
Abstracts. Twenty-second European Workshop on Computational Geometry: 6th Italian Conference, Ciac 2006, Rome, Italy, May 29-31, 2006. Proceedings, 2006, p. 177-180
Main Research Area:
Lecture Notes in Computer Science
22nd European Workshop on Computational Geometry. EWCG 2006