Phase changes in random point quadtrees

Hua Huai Chern; Michael Fuchs; Hsien Kuei Hwang

doi:10.1145/1240233.1240235

Phase changes in random point quadtrees

Hua Huai Chern, Michael Fuchs, Hsien Kuei Hwang^*

^*Corresponding author for this work

Department of Applied Mathematics

Research output: Contribution to journal › Article › peer-review

15 Scopus citations

Abstract

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.

Original language	English
Article number	1240235
Journal	ACM Transactions on Algorithms
Volume	3
Issue number	2
DOIs	https://doi.org/10.1145/1240233.1240235
State	Published - 1 May 2007

Keywords

Analysis in distribution of algorithms
Asymptotic transfer
Central limit theorems
Depth
Differential equations
Grid trees
Local limit theorems
Mellin transforms
Page usage
Phase transitions
Quadtrees
Total path length

Access to Document

10.1145/1240233.1240235

Link to publication in Scopus

Fingerprint Dive into the research topics of 'Phase changes in random point quadtrees'. Together they form a unique fingerprint.

Cite this

@article{cd660ae4e8ee438db3d6ccb0d9e899f5,

title = "Phase changes in random point quadtrees",

abstract = "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.",

keywords = "Analysis in distribution of algorithms, Asymptotic transfer, Central limit theorems, Depth, Differential equations, Grid trees, Local limit theorems, Mellin transforms, Page usage, Phase transitions, Quadtrees, Total path length",

author = "Chern, {Hua Huai} and Michael Fuchs and Hwang, {Hsien Kuei}",

year = "2007",

month = may,

day = "1",

doi = "10.1145/1240233.1240235",

language = "English",

volume = "3",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery (ACM)",

number = "2",

}

TY - JOUR

T1 - Phase changes in random point quadtrees

AU - Chern, Hua Huai

AU - Fuchs, Michael

AU - Hwang, Hsien Kuei

PY - 2007/5/1

Y1 - 2007/5/1

N2 - 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.

AB - 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.

KW - Analysis in distribution of algorithms

KW - Asymptotic transfer

KW - Central limit theorems

KW - Depth

KW - Differential equations

KW - Grid trees

KW - Local limit theorems

KW - Mellin transforms

KW - Page usage

KW - Phase transitions

KW - Quadtrees

KW - Total path length

UR - http://www.scopus.com/inward/record.url?scp=34250222447&partnerID=8YFLogxK

U2 - 10.1145/1240233.1240235

DO - 10.1145/1240233.1240235

M3 - Article

AN - SCOPUS:34250222447

VL - 3

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

SN - 1549-6325

IS - 2

M1 - 1240235

ER -