DESIGNING EFFICIENT GEOMETRIC SEARCH ALGORITHMS USING PERSISTENT BINARY-BINARY SEARCH-TREES

Authors
TAN XH HIRATA T INAGAKI Y
Citation
Xh. Tan et al., DESIGNING EFFICIENT GEOMETRIC SEARCH ALGORITHMS USING PERSISTENT BINARY-BINARY SEARCH-TREES, IEICE transactions on fundamentals of electronics, communications and computer science, E77A(4), 1994, pp. 601-607
Citations number
NO
Categorie Soggetti
Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture","Computer Science Information Systems
Journal title
IEICE transactions on fundamentals of electronics, communications and computer science → ACNP
ISSN journal
09168508
Volume
E77A
Issue
4
Year of publication
1994
Pages
601 - 607
Database
ISI
SICI code
0916-8508(1994)E77A:4<601:DEGSAU>2.0.ZU;2-V
Abstract
Persistent data structures, introduced by Sarnak and Tarjan, have been found especially useful in designing geometric algorithms. In this pa per, we present a persistent form of binary-binary search tree, and th en apply this data structure to solve various geometric searching prob lems, such as, three dimensional ray-shooting, hidden surface removal, polygonal point enclosure searching and so on. In all applications, w e are able to either improve existing bounds or establish new bounds.