DOC PREVIEW
Duke CPS 296.2 - Ray shooting and Parametric Search

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

AbstractRay shooting and Parametric Search *Pankaj K. Agarwalt and Jiii Matou5ek$We present efficient algorithms for the ray shooting prob-lem: Given a collection 17of obiects in IIRd,build a datastructure, so that one can quic~-y determine the first ob-ject of 1?hit by a query ray. Using the parametric searchtechnique, we reduce thk problem to the segment ernpt:-ness problem. For various ray shooting problems, weachieve space/query time tradeoffs of the following type:for some integer b and a parameter m (n < m < nb)the queries are answered in time 0(--& logO(l) n),With.O(ml+’ ) space and preprocessing time (e >0 is arbitrar-ily small but fixed). We get b = [d/2] for ray shootingin a convex d-poly-tope defined as an intersection of nhalf-spaces, b = d- fo; an arrangement of n hyperplanesin R d and b = 3 for an arrangement of n half-planes inR3. Next we apply the ray shooting algorithms to sev-eral problems including reporting k-nearest (or k-farthest)neighbors, hidden surface removal, computing convex lay-ers, and computing levels in arrangements of planes. Allthe algorithms described here either give the first non-trivial solutions to these problems, or improve the previ-ously best known solutions significantly.*Work by the first author has been supported by NationalScience Foundation Grant CCR-91-06514.t Computer Science Department, Duke University, Durham,NC 27706.$Dep=tment of Applied Mathematics, Charles University,Praha.Permission to copy without fee all or part of this material isgranted provided that the copies are not made or distributed fordirect commercial advantage, the ACM copyright notice and thetitle of the publication and its date appear, and notice ia giventhat copying is by permission of the Association for ComputingMachinery. To copy otherwise, or 10 republish, requires a feeand/or specific permission.24th ANNUAL ACM STOC - 5/92/VICTORIA, B. C., CANADA~ 1992 ACM 0-89791-51 2.7\92/0004/05J 7...$J .5r31 IntroductionConsider the following ray shooting problem: Givenacollection I’ of n objects in IRd, build a data struc-tures, so that one can quickly determine the jirst ob-ject of r intersected by a query ray.The ray shooting problem has received a lot ofattention in the last few years because of its ap-plications in graphics and other geometric problems[11, 20, 1, 5, 7]. But most of the work done so farhas been for the planar case where 17is a collection ofline segments in IR2. Chazelle and Guibas proposedan optimal algorithm for the special case where 17isthe boundary of a simple polygon [11]. Their algo-rithm answers a ray shooting query in O(log n) timeusing O(n) space. If I’ is a collection of arbitrary seg-ments in the plane, the best known algorithm answersa ray shooting query in time 0( ~ logO(l) n) usingO(rnl+’) space and preprocessing [1, 5]. Althoughno lower bound is known for this case, it is conjec-tured that this bound is close to optimal. But theproblem is far from being solved in three and higherdimensions. For example, no efficient ray shooting al-gorithm haa been known for a convex d-polytope ford > 3. Even in IR3, non-trivial solutions have beenobtained only very recently (cf. [5, 7]).In this paper, we present ray shooting algorithmsfor several cases in higher dimensions (d z 3), includ-ing a convex polytope, a collection of n hyperplanesin IRd, and a collection of n half-planes in R3.We willuse a unified approach for all cases, which is, roughlyspeaking, a binary search along the query ray p. Inorder to make this approach work, we need to handletwo problems: (i) Perform a binary search withoutcomputing all intersection points of p and the objectsof I’, and (ii) Given a point z c p, determine whether* Throughout this paper, e denotes an arbitrarily small pos-itive constant. The multiplicative constants in the asymptoticbounds may depend on e.517the first intersection point of r and p lies before orafter x.To handle the first problem we perform an implicitbinary search using the parametric search techniqueof Megiddo [25], and, to handle the second problem,we use suitable range searching structures for detect-ing an intersection between p and the objects of I’.Our approach can be easily extended to report thefirst k objects hit by the query ray.The range searching algorithms, we have at dis-posal, usually admit time/space tradeoffs: the morespace (and preprocessing time) we use, the faster thequeries can be answered. Sucha tradeoff then trans-fers to the ray shooting results. A usual form of thistradeoff is the following: There are two fixed integersb, c (specific to the considered problem), such thatwith O(rnl+S) space and preprocessing time, wheren < m < nb, a query can be answered in time0( ~ log’ n). Note that since we require m ~ n, thesmallest amount of space we consider in this tradeoffis O(n l+C). Hence the loge n factor plays a role onlywhen m is close to nb; actually it expresses the querycomplexity for the maximum permissible amount ofspace. For the sake of brevity, we just say that such aproblem admits ad andard tradeofl with certain valueof b. It is understood that c is always a (reasonablysmall) constant.We first describe the general ray shooting algo-rithm (Section 2), and then apply this technique toobtain fast procedures for the following specific in-st antes (Section 3): H yperplanes in Rd.Previ-ously, efficient solutions were known only for d <3 [5].Moreover, they did not support insertion/deletion ofplanes for d = 3. We obtain a data structure withquery time 0(* log4 n).Convex d-polytope. We assume that the poly-topes is defined as the intersection of n half-spaces.For d = 2 a straight-forward binary search can an-swer a ray shooting query in O(log n) time, and ford= 3 one can use Dobkin-Kirkpatrick hierarchicalrepresentation of a 3-polytope to obtain an optimalalgorithm [17]. But for d > 3, Dobkin-Kirkpatrickhierarchical representation does not work, and no ef-ficient algorithm is known for ray shooting in higherdimensions. Even in 1113no efficient ray shooting al-gorithm is known if the polytopeP changes dynam-ically. We present a data structure with query time0( “m*j-log5 n).Half-planes in R3, The previously best knownresult answered a query in time 0( “~~~fi= ) usingO(ml+’ ) space and preprocessing [5]. We present adata structure with query time O(* log3 n).Next, we apply the above ray shooting algorithmsfor various other problems:Proximity problems. Clarkson showed that if weallow O(n [df21 +’ )


View Full Document

Duke CPS 296.2 - Ray shooting and Parametric Search

Download Ray shooting and Parametric Search
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Ray shooting and Parametric Search and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Ray shooting and Parametric Search 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?