Titlebook: Algorithms and Data Structures; Workshop WADS ‘89, O F. Dehne,J. -R. Sack,N. Santoro Conference proceedings 1989 Springer-Verlag Berlin Hei

DEFT

变色龙

Armando Häring,Thomas Klein,Kristian StoyeFredman and Saks [1] have proved a Ω(log ./log log .) amortized time lower bound for two problems, List Indexing and Subset Rank, in the cell probe model with logarithmic word size. This paper gives algorithms for both problems that achieve the lower bound on a RAM with logarithmic word size.

Foolproof

Björn Schneider Diplom-SoziologeLet p and q be a pair of points in a set S of N points in the plane. Let d(p,q) be the Euclidean distance between p and q and let DT(p,q) be the length of the shortest path from p to q in the Delaunay triangulation of S. We show that that the ratio . independent of S and N.

镇压

LUDE

Optimal algorithms for List Indexing and Subset Rank,Fredman and Saks [1] have proved a Ω(log ./log log .) amortized time lower bound for two problems, List Indexing and Subset Rank, in the cell probe model with logarithmic word size. This paper gives algorithms for both problems that achieve the lower bound on a RAM with logarithmic word size.

伟大

figment

青春期

幼儿

ostensible

On the performance of orthogonal range queries in multiattribute and doubly chained trees,we study the effect of page size variation in a paginated tree. We show that pagination may decrease the search cost, but is liable to raise the access cost in considerable proportion with respect to the cost on a non paginated tree.