An optimal two-dimensional orthogonal range search algorithm in VLSI, design automation

Author

Pan, Yu-Hsiang ; Lee, Kuo-Tien ; Wang, Yung-Hung

Author_Institution

Dept. of Environ. Biol. & Fisheries, Nat. Taiwan Ocean Univ., Keelung, Taiwan

Volume

1

fYear

2010

fDate

5-7 May 2010

Firstpage

53

Lastpage

56

Abstract

It is well known that an optimal algorithm for logarithm query time and linear storage for two dimensional orthogonal range searches is nonexistent except for very few cases in which certain computational models have been assumed. A new algorithm called sliding kd tree is presented in this article where the length of the query box is fixed in any direction. The new algorithm is optimal in handling two-dimensional problems, and can be applied to VLSI Design Automations presented to show the performance of the SKD algorithm.

Keywords

VLSI; integrated circuit design; search problems; trees (mathematics); SKD algorithm; VLSI design automation; linear storage; logarithm query time; optimal two-dimensional orthogonal range search algorithm; sliding kd tree algorithm; Biological control systems; Biology computing; Communication system control; Computational biology; Computational modeling; Design automation; Optimal control; Storage automation; Underwater communication; Very large scale integration; VLSI; optimal algorithm; slidung kd tree;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Communication Control and Automation (3CA), 2010 International Symposium on

Conference_Location

Tainan

Print_ISBN

978-1-4244-5565-2

Type

conf

DOI

10.1109/3CA.2010.5533737

Filename

5533737