Practical Efficiencies of Planar Point Location Algorithms

Satoshi KAGAMI
Masato EDAHIRO
Takao ASANO

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E77-A    No.4    pp.608-614
Publication Date: 1994/04/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
algorithms,  computational geometry,  data structures,  point location,  practical efficiency,  

Full Text: PDF(588.8KB)>>
Buy this Article



Summary: 
The planar point location problem is one of the most fundamental problems in computational geometry and stated as follows: Given a straight line planar graph (subdivision) with n vertices and an arbitary query point Q, determine the region containing Q. Many algorithms have been proposed, and some of them are known to be theoretically optimal (O(log n) search time, O(n) space and O(n log n) preprocessing time). In this paper, we implement several representative algorithms in C, and investigate their practical efficiencies by computational experiments on Voronoi diagrams with 210 - 217 vertices.