Abstract | ||
---|---|---|
We solve the open problem of characterizing the leading constant in the asymptotic approximation to the expected cost used for random partial match queries in random k-d trees. Our approach is new and of some generality; in particular, it is applicable to many problems involving differential equations (or difference equations) with polynomial coefficients. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1137/S0097539703437491 | SIAM J. Comput. |
Keywords | Field | DocType |
difference equation,partial match queries,differential equation,open problem,method of linear operators,expected cost,average-case analysis of algorithms,k-d trees,asymptotic analysis,random k-d trees,random k-d tree,polynomial coefficient,asymptotic approximation,random partial match query,differential equations,mellin transform,linear operator,asymptotic expansion,binomial transform,k d tree | Generating function,Differential equation,Discrete mathematics,Combinatorics,Tree (graph theory),Open problem,Recurrence relation,k-d tree,Binomial transform,Asymptotic analysis,Mathematics | Journal |
Volume | Issue | ISSN |
35 | 6 | 0097-5397 |
Citations | PageRank | References |
14 | 0.72 | 29 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hua-Huai Chern | 1 | 78 | 7.25 |
Hsien-Kuei Hwang | 2 | 365 | 38.02 |