Browsing by Author "Chern, Hua-Huai"

Now showing 1 - 2 of 2

Dependence and phase changes in random m-ary search trees
(2017-05-01)
Chern, Hua-Huai
;
Fuchs, Michael
;
Hwang, Hsien-Kuei
;
Neininger, Ralph
;
應用數學系
We study the joint asymptotic behavior of the space requirement and the total path length (either summing over all root-key distances or over all root-node distances) in random m-ary search trees. The covariance turns out to exhibit a change of asymptotic behavior: it is essentially linear when 3m13, but becomes of higher order when m14. Surprisingly, the corresponding asymptotic correlation coefficient tends to zero when 3m26, but is periodically oscillating for larger m, and we also prove asymptotic independence when 3m26. Such a less anticipated phenomenon is not exceptional and our results can be extended in two directions: one for more general shape parameters, and the other for other classes of random log-trees such as fringe-balanced binary search trees and quadtrees. The methods of proof combine asymptotic transfer for the underlying recurrence relations with the contraction method. (c) 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 353-379, 2017
Phase Changes in Random Point Quadtrees
(2007-05-01)
Chern, Hua-Huai
;
Fuchs, Michael
;
Hwang, Hsien-Kuei
;
應用數學系
;
Department of Applied Mathematics
We show that a wide class of linear cost measures (such as the number of leaves) in random d-dimensional point quadtrees undergo a change in limit laws: If the dimension d = 1, ..., 8, then the limit law is normal; if d >= 9 then there is no convergence to a fixed limit law. Stronger approximation results such as convergence rates and local limit theorems are also derived for the number of leaves, additional phase changes being unveiled. Our approach is new and very general, and also applicable to other classes of search trees. A brief discussion of Devroye's grid trees (covering m-ary search trees and quadtrees as special cases) is given. We also propose an efficient numerical procedure for computing the constants involved to high precision.