Publication Details
Author: L. J. Guibas and M. Pellegrini
Group: ICSI Technical Reports
Date: February 1992
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-92-005.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-92-005
Bibliographic Reference:
L. J. Guibas and M. Pellegrini. New Algorithmic Results for Lines-in-3-Space Problems. ICSI Technical Report TR-92-005, February 1992