On Constant Factors in Comparison-Based Geometric Algorithms and Data Structures
Timothy M. Chan, Patrick P. C. Lee · 2014
Many standard problems in computational geometry have been solved asymptotically optimally as far as comparison-based algorithms are concerned, but there has been little work focusing on improving the constant factors hidden in big-Oh bounds on the number of comparisons needed. In this paper, we consider orthogonal-type problems and present a number of results that achieve optimality in the constant factors of the leading terms, including: