Ray shooting and stone throwing with near-linear storage

摘要

The paper presents two algorithms involving shooting in three dimensions. We first present an algorithm for performing ray shooting amid several special classes of n triangles in three dimensions, including sets of fat triangles, and sets of triangles stabbed by a common line. In all these special cases, our technique requires near-linear preprocessing and storage, and answers a query in O(n(2/3+epsilon)) time. This improves the best known result of O(n (3/4+epsilon)) query time (with near-linear storage) for general triangles. The second algorithm handles stone-throwing amid arbitrary triangles in 3-space, where the curves along which we shoot are vertical parabolic arcs that are trajectories of stones thrown under gravity. We present an algorithm that answers stone-throwing queries in O(n (3/4+epsilon)) time, using near linear storage and preprocessing. As far as we know, this is the first nontrivial solution of this problem. Several extensions of both algorithms are also presented. (c) 2004 Elsevier B.V. All rights