New Algorithmic Results for Lines-in-3-Space Problems

In the first part of the report we consider some incidence and ordering problems for lines in 3-space. We solve the problem of detecting efficiently if a query simplex is collision-free among polyhedral obstacles. In order to solve this problem we develop new on-line data structures to detect intersections of query halfplanes with sets of lines and segments.Then, we consider the nearest-neighbor problems for lines. Given a set of$n$ lines in 3-space, the shortest vertical segment between any pair of lines is found in randomized expected time $O(n^{8/5+epsilon})$ for every $eps>0$. The longest connecting vertical segment is found in time $O(n^{4/3+eps})$. The shortest connecting segment is found in time $O(n^{5/3 + epsilon})$.Problems involving lines, points and spheres in 3-space have important applications in graphics, CAD and optimization. In the second part of the report we consider several problems of this kind. We give subquaratic algorithms to count the number of incidences between a set of lines and a set of spheres, and to find the minimum distance between a set of lines and a set of points. We show that the sphere of minimum radius intersecting every line in a set of $n$ lines can be found in optimal expected time $O(n)$. Given $m$ possibly intersecting spheres we solve ray-shooting queries in $O(log^2 m)$ time using a data structure of size $O(m^{5+eps})$.This technical report collects part of the second author's work at ICSI from September 1991 to January 1992.

ICSI Technical Report TR-92-005

Technical Report