This paper introduces a solution to dynamic rectangle intersection searching problem.There are two semi-dynamic algorithms which are based on 1-dimensional data structure and 2-dimensional data structure respectively.The computational complexity Of 1-D searching algorithm is as follows:query time O(1ogM+k'),update time O(1ogMlogn),space O(nlogM).The computational complexity of 2-D searching algorithm is as follows:query time O(1og2M+k),update time O(1og2Mlogn),space O(nlog2M).The two algorithms are implemented respectively.With an experimental comparison,the authors found that 1-D searching algorithm is far better than 2-D searching algorithm.
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.