# Suppose you are hiking in the wild country of some exotic part of the world. Naturally, an important part of your survival gear is a GPS tracking device and a digital map of the region you are hiking in, which includes the pathways of trails, rivers, and creeks, as well as obstacles like cliffs and mountains. These pathways and obstacles

Chapter 22, Application #6

Suppose you are hiking in the wild country of some exotic part of the world. Naturally, an important part of your survival gear is a GPS tracking device and a digital map of the region you are hiking in, which includes the pathways of trails, rivers, and creeks, as well as obstacles like cliffs and mountains. These pathways and obstacles are described on your map by a collection, S, of n twodimensional line segments that may intersect only at their endpoints (hence, no pair of segments in S cross). In order to locate your position on this map, however, you need to identify where your current position, (x, y), lies in reference to the segments in S. Such a query can be satisfied by imagining that we shoot a vertical ray up or down from the point, (x, y), to the first segment that it hits in S, which is known as a vertical ray-shooting query. In order to facilitate such a query, it is desirable for us to process the segments in S to define a trapezoidal decomposition of the plane. Such a decomposition is defined by shooting vertical rays up and down from every endpoint of a segment in S until it hits another segment in S or it hits the boundary of the map. In the map defined by S and these vertical rays, every face is either a trapezoid or a triangle. This partitioning allows us to then construct a data structure for answering vertical ray-shooting queries, since such a query can be answered simply by identifying the face in the trapezoidal decomposition that contains the starting point for the ray. Thus, given a set, S, of n line segments that may intersect only at their endpoints, describe an O(n log n)-time algorithm for constructing a trapezoidal decomposition of S.