Average Case Analysis of an Adjacency Map Searching Technique.

Abstract

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 0(nlogn), searched in time 0(logn), and stored in space 0(n). Though asymptotically optimal, the previous algorithms are not very practical. More practical algorithms have been proposed (Preparata, Preparata-Lipski), which use 0(nlogn) 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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1981
Accession Number
ADA124473

Entities

People

  • Gianfranco Bilardi

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Contracts
  • Discriminators
  • Electrical Engineering
  • Generators
  • Geometry
  • Illinois
  • Preprocessing
  • Probabilistic Models
  • Probability
  • Random Variables
  • Security
  • Simulations
  • Trees (Data Structures)
  • Two Dimensional
  • Universities

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research
  • Parallel and Distributed Computing.

Technology Areas

  • Space