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

Xuehou TAN; Tomio HIRATA; Yasuyoshi INAGAKI

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

Xuehou TAN, Tomio HIRATA, Yasuyoshi INAGAKI

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E77-A No.4 pp.601-607

Publication Date: 1994/04/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Xuehou TAN, Tomio HIRATA, Yasuyoshi INAGAKI, "Designing Efficient Geometric Search Algorithms Using Persistent Binary-Binary Search Trees" in IEICE TRANSACTIONS on Fundamentals, vol. E77-A, no. 4, pp. 601-607, April 1994, doi: .
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e77-a_4_601/_p

Copy

@ARTICLE{e77-a_4_601,
author={Xuehou TAN, Tomio HIRATA, Yasuyoshi INAGAKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Designing Efficient Geometric Search Algorithms Using Persistent Binary-Binary Search Trees},
year={1994},
volume={E77-A},
number={4},
pages={601-607},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - Designing Efficient Geometric Search Algorithms Using Persistent Binary-Binary Search Trees
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 601
EP - 607
AU - Xuehou TAN
AU - Tomio HIRATA
AU - Yasuyoshi INAGAKI
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E77-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 1994
AB - 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.
ER -