VARIATIONS ON RAY SHOOTING

We solve some problems related to ray shooting in the plane, such as f inding the first object hit by a query ray or counting the number of o bjects intersected by the query line. Our main results are an algorith m for finding the first hit when the objects are lines, and an algorit hm for the case when the objects are segments. If the segments form si mple polygons, this information can be used for reducing the complexit y of the algorithms. The algorithms are efficient in space and in quer y time. Moreover, they are simple and therefore of practical use.