A New Approach to Planar Point Location.

Abstract

Given a planar straight line graph G with n vertices and a point PO, locating PO means to find the region of the planar subdivision induced by G which contains PO. Recently, Lipton and Tarjan presentd a brillian but extremely complex point location algorithm which runs in time 0(logn) on a data structure using 0(n) storage. This paper presents a practical algorithm which runs in less than 6 (log2n) comparisons on a data structure which uses 0(nlogn) storage, in the worst case. The method rests crucially on a simple partition of each edge of G into 0(logn) segments. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1978
Accession Number
ADA069833

Entities

People

  • Franco P. Preparata

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Air Platforms
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Algorithms
  • Computational Science
  • Computer Science
  • Computer Vision
  • Construction
  • Digital Information
  • Electrical Engineering
  • Engineering
  • Illinois
  • Security
  • Sequences
  • Three Dimensional
  • Trees (Data Structures)
  • United States
  • United States Government

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Information Retrieval