On the relative complexities of some geometric problems

Proceedings of the 7th Canadian Conference on Computational Geometry, 85-90, 1995.

Invited to the special issue of Computational Geometry: Theory and Applications devoted to the conference.

We consider the relative complexities of a number of problems whose complexities are believed to be roughly Theta(n4/3). That is, for certain pairs of problems, we show that the complexity of one problem is asymptotically bounded by the complexity of the other. Each of the problems we consider can be solved in time O(n4/3+delta) or better, and there are Omega(n4/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 formally harder than Hopcroft's problem. These problems include various ray shooting problems, sorting line segments in R3, collision detection in R3, and halfspace emptiness checking in R5. In the second, we survey known reductions among problems involving lines in three-space, and among higher dimensional closest-pair problems. Some of our results rely on the introduction of formal infinitesimals during reduction; we show that such a reduction is meaningful in the algebraic decision tree model.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 15 Nov 1999