A New Approach to Planar Point Location.

reportActive / Technical Report | Accession Number: ADA069833 | Open PDF

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 0logn on a data structure using 0n storage. This paper presents a practical algorithm which runs in less than 6 log2n comparisons on a data structure which uses 0nlogn storage, in the worst case. The method rests crucially on a simple partition of each edge of G into 0logn segments. Author

Author(s):
Preparata, Franco P.
Author Organization(s):
ILLINOIS UNIV AT URBANA-CHAMPAIGN APPLIED COMPUTATION THEORY GROUP
Descriptive Note:
Technical rept.,
Supplementary Note:
Also available as Rept. no. R-829.
Pagination:
0029

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
ACT-11, UILU-ENG-78-2222
Contract/Grant Number(s):
DAAB07-72-C-0259, NSF-MSC76-17321
 Subject Terms
Joint Capability Areas:
JCA_1_Force Support; JCA_5_Command and Control; JCA_1.2_Force Preparation; JCA_6.4.1_Secure Information Exchange; JCA_5.3_Planning; JCA_1.3_Human Capital Management; JCA_6.4_Information Assurance; JCA_6_Net Centric
Modernization Areas:
AI and Machine Learning
Communities of Interest:
Air Platforms
Descriptor(s):
*GRAPHS, *LOCATORS, ALGORITHMS, COMPUTATIONS, NODES, POSITION FINDING, LOGARITHM FUNCTIONS
Field(s)/Group(s):
Theoretical Mathematics
Keyword(s):
Trees(Mathematics)
Report Date:
1978 Oct 01