Line problems in nonlinear computational geometry
Frank Sottile, Thorsten Theobald · Contemporary mathematics - American Mathematical Society · 2008
Abstract. We first review some topics in the classical computational geometry of lines, in particular the O(n 3+ǫ) bounds for the combinatorial complexity of the set of lines in R 3 interacting with n objects of fixed description complexity. The main part of this survey is recent work on a core algebraic problem—studying the lines tangent to k spheres that also meet 4−k fixed lines. 1.