Average Case Analysis of an Adjacency Map Searching Technique.

The adjacency map is a data structure a tree used to solve the following problem given a set of parallel segments in the plane and a point p, find the segments closest to p among those intersected by the straight line through p, perpendicular to the common direction of the segments. The search is performed in the repetitive mode, so that preprocessing is convenient. The problem considered is a particular case of planar point location for which algorithms are known Lipton-Tarjan, Kirkpatrick, which make use of data structures constructed in time 0nlogn, searched in time 0logn, and stored in space 0n. Though asymptotically optimal, the previous algorithms are not very practical. More practical algorithms have been proposed Preparata, Preparata-Lipski, which use 0nlogn space. In this thesis a modification of these algorithm is presented for the adjacency map, and the worst case analysis is performed. The technique is easily extensible to general planar graphs. It is conjectured that, under reasonable assumptions on the input distribution, the new algorithm takes expected linear storage. Author