On Collision-Free Placements of Simplices and the Closest Pair of Lines in 3-Space
Marco Pellegrini · SIAM Journal on Computing · 1994
The problem of detecting efficiently whether a query simplex is collision free among polyhedral obstacles is considered. If n is the number of vertices, edges, and faces of the polyhedral obstacles, and m is the amount of storage allocated for the data structure $(n^{1 + \epsilon } \leqslant m \leqslant n^{4 + \epsilon } )$, it is possible to solve collision-free placements queries for simplices in time $O({{n^{1 + \epsilon } } / {m^{{1 / 4}} }})$ for any $ \epsilon > 0$, where the constants depend on $ \epsilon $. In order to solve this problem the authors develop data structures to detect on-line intersections of query half planes with sets of lines and segments. Some nearest-neighbor problems for objects in 3-space are also considered. 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 $ \epsilon > 0$. The longest connecting vertical segment is found in time $O(n^{{4 / 3} + \in } )$ The shortest connecting segment is found in time $O(n^{{5 / 3} + \epsilon } )$.