Designing Efficient Geometric Search Algorithms Using Persistent Binary-Binary Search Trees

Xuehou TAN  Tomio HIRATA  Yasuyoshi INAGAKI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E77-A   No.4   pp.601-607
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: 
computational geometry,  persistent data structures,  persistent binary-binary search trees,  ray-shooting,  

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




Summary: 
Persistent data structures, introduced by Sarnak and Tarjan, have been found especially useful in designing geometric algorithms. In this paper, we present a persistent form of binary-binary search tree, and then apply this data structure to solve various geometric searching problems, such as, three dimensional ray-shooting, hidden surface removal, polygonal point enclosure searching and so on. In all applications, we are able to either improve existing bounds or establish new bounds.