On the relative complexities of some geometric problems.
Jeff Erickson · 1995
We consider the relative complexities of a large number of computational geometry problems whose complexities are believed to be roughly \\Theta(n 4=3 ). For certain pairs of problems, we show that the complexity of one problem is asymptotically bounded by the complexity of the other. Almost all of the problems we consider can be solved in time O(n 4=3+ffi ) or better, and there are\\Omega n 4=3 )lower bounds for a few of them in specialized models of computation. However, the best known lower bound in any general model of computation is only\\Omega (n log n). The paper is naturally divided into two parts. In the first part, we consider a large number of problems that are harder than Hopcroft's problem. These problems include various ray shooting problems, sorting line segments in IR 3 , collision detection in IR 3 , and halfspace emptiness checking in IR 5 . In the second, we survey known reductions among problems involving lines in three-space, and among highe...