Сотрудники :: Гасанов Эльяр Эльдарович :: Публикации Гасанова Э.Э.
On one method to decrease average search time
Elyar E. Gasanov and Irina V. Kuznetsova Moscow State University, Russia
We will consider twodimensional
range searching. Let Y=[0,1]x[0,1]. X={x=(u,v,w,z): 0<u<v<1, 0<w<z<1}
be a set of inquires. r – relation on XxY such that for any x=(u,v,w,z)
from X
and y=(p,q)
from Y x r y
if and only if u<p<v &
w<q<z. V
be a finite subset of Y. Twodimensional range searching
consists in enumeration for any inquire x from X all that and only that objects y from
V,
such that x
r y. Three characteristics (amount of memory, worstcase search time
and average search time) are usually used for estimation of search algorithms.
Say search algorithm is (f(k),g(k),h(k))algorithm if amount of memory,
worstcase search time and average search time of this algorithm are equal to O(f(k)),
O(g(k))
and O(h(k))
correspondingly when k becomes infinite, there k=V.
(exp(3 ln k),
log k,
log k)algorithm [1] and (exp((1+a) ln k), log k, log k)algorithm (0<a<1)
[2],solving twodimensional range searching, are known. We suggest some method
of modification of these algorithms, which leads to (exp(3 ln k), log k, 1)algorithm [3]
and (exp((1+a)
ln k),
log k,
1)algorithm.
Reference:
[1]
J.L.Bentley, Decomposable searching problems. Info. Proc. Lett. (1979) 8,
244251.
[2]
J.L.Bentley, H.A.Mayrer, Efficient worstcase data structures for range
searching. Acta
Informatica (1980) 13, 155168.
[3]
E.E.Gasanov, Instantly solvable search problems. Discrete Mathematics and Applications
(1996) 6, 467482.
Abstracts of I Turkish World Mathematics Symposium Elazig, Turkey (29 June – 2 July 1999).
Наверх
