{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,21]],"date-time":"2026-09-21T21:46:30Z","timestamp":1790027190558,"version":"4.0.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[1993,12,1]],"date-time":"1993-12-01T00:00:00Z","timestamp":754704000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1993,12]]},"DOI":"10.1007\/bf01891833","type":"journal-article","created":{"date-parts":[[2005,7,5]],"date-time":"2005-07-05T03:18:01Z","timestamp":1120533481000},"page":"473-500","source":"Crossref","is-referenced-by-count":47,"title":["Analytic variations on quadtrees"],"prefix":"10.1007","volume":"10","author":[{"given":"Philippe","family":"Flajolet","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gaston","family":"Gonnet","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Claude","family":"Puech","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J. M.","family":"Robson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01891833_CR1","volume-title":"Handbook of Mathematical Functions","author":"M. Abramowitz","year":"1973","unstructured":"Abramowitz, M., and Stegun, I. A.Handbook of Mathematical Functions. Dover, New York, 1973. A reprint of the tenth National Bureau of Standards edition, 1964."},{"issue":"9","key":"BF01891833_CR2","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"J. L. Bentley","year":"1975","unstructured":"Bentley, J. L.: Multidimensional binary search trees used for associative searching.Communications of the ACM,18(9) (Sept. 1975), 509\u2013517.","journal-title":"Communications of the ACM"},{"issue":"4","key":"BF01891833_CR3","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1145\/356789.356797","volume":"11","author":"J. L. Bentley","year":"1979","unstructured":"Bentley, J. L., and Friedman, J. H.: Data structures for range searching.ACM Computing Surveys,11(4) (1979), 397\u2013409.","journal-title":"ACM Computing Surveys"},{"issue":"6","key":"BF01891833_CR4","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1016\/0020-0190(75)90034-4","volume":"3","author":"J. L. Bentley","year":"1975","unstructured":"Bentley, J. L., and Stanat, D. F.: Analysis of range searching in quad trees.Information Processing Letters,3(6) (July 1975), 170\u2013173.","journal-title":"Information Processing Letters"},{"key":"BF01891833_CR5","unstructured":"Bronstein, M. On solutions of linear ordinary differential equations in their coefficient field. Technical Report 152, Department Informatik, ETH, January 1991."},{"key":"BF01891833_CR6","unstructured":"Bronstein, M. Rational solution to differential equations related to quadtrees. Private communication, February 1991."},{"key":"BF01891833_CR7","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0020-0190(89)90156-7","volume":"33","author":"C. Buchta","year":"1989","unstructured":"Buchta, C.: On the average number of maxima in a set of vectors.Information Processing Letters,33 (Nov. 1989), 63\u201365.","journal-title":"Information Processing Letters"},{"key":"BF01891833_CR8","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BF00265991","volume":"24","author":"L. Devroye","year":"1987","unstructured":"Devroye, L.: Branching processes in the analysis of the heights of trees.Acta Informatica,24 (1987), 277\u2013298.","journal-title":"Acta Informatica"},{"key":"BF01891833_CR9","doi-asserted-by":"crossref","first-page":"821","DOI":"10.1137\/0219057","volume":"19","author":"L. Devroye","year":"1990","unstructured":"Devroye, L., and Laforest, L.: An analysis of randomd-dimensional quad trees.SIAM Journal on Computing,19 (1990), 821\u2013832.","journal-title":"SIAM Journal on Computing"},{"key":"BF01891833_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF00288933","volume":"4","author":"R. A. Finkel","year":"1974","unstructured":"Finkel, R. A., and Bentley, J. L.: Quad trees, a data structure for retrieval on composite keys.Acta Informatica,4 (1974), 1\u20139.","journal-title":"Acta Informatica"},{"key":"BF01891833_CR11","unstructured":"Fishburn, P. C., Odlyzko, A. M., and Roberts, F. S. Two-sided generalized Fibonacci sequences. Preprint, 1989."},{"key":"BF01891833_CR12","doi-asserted-by":"crossref","unstructured":"Flajolet, P., and Lafforgue, T. Search costs in quadtrees and singularity perturbation asymptotics. 1993, submitted.","DOI":"10.1007\/BF02574372"},{"key":"BF01891833_CR13","first-page":"100","volume-title":"The analysis of multidimensional searching in quad-trees","author":"P. Flajolet","year":"1991","unstructured":"Flajolet, P., Gonnet, G., Puech, C., and Robson, J. M. The analysis of multidimensional searching in quad-trees.Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, 1991, SIAM, Philadelphia, PA, pp. 100\u2013109."},{"issue":"2","key":"BF01891833_CR14","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0403019","volume":"3","author":"P. Flajolet","year":"1990","unstructured":"Flajolet, P., and Odlyzko, A. M.: Singularity analysis of generating functions.SIAM Journal on Discrete Mathematics,3(2) (1990), 216\u2013240.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"2","key":"BF01891833_CR15","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1145\/5383.5453","volume":"33","author":"P. Flajolet","year":"1986","unstructured":"Flajolet, P., and Puech, C.: Partial match retrieval of multidimensional data.Journal of the ACM,33(2) (1986), 371\u2013407.","journal-title":"Journal of the ACM"},{"key":"BF01891833_CR16","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0097-3165(90)90056-3","volume":"53","author":"P. Flajolet","year":"1990","unstructured":"Flajolet, P., and Soria, M.: Gaussian limiting distributions for the number of components in combinatorial structures.Journal of Combinatorial Theory, Series A,53 (1990), 165\u2013182.","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"BF01891833_CR17","volume-title":"Handbook of Algorithms and Data Structures: in Pascal and C","author":"G. H. Gonnet","year":"1991","unstructured":"Gonnet, G. H., and Baeza-Yates, R.Handbook of Algorithms and Data Structures: in Pascal and C, second edn. Addison-Wesley, Reading, MA, 1991.","edition":"second edn."},{"issue":"4","key":"BF01891833_CR18","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0196-6774(82)90031-1","volume":"3","author":"L. Guibas","year":"1982","unstructured":"Guibas, L.: Problems.Journal of Algorithms,3(4) (1982), 362\u2013380. \u2329Problem 80-6\u232a, from the Stanford 1979 Algorithms Qualifying Examination. Solution by Eric S. Rosenthal, pp. 368\u2013371.","journal-title":"Journal of Algorithms"},{"key":"BF01891833_CR19","volume-title":"Applied and Computational Complex Analysis","author":"P. Henrici","year":"1977","unstructured":"Henrici, P.Applied and Computational Complex Analysis. Wiley, New York, 1977. Three volumes."},{"key":"BF01891833_CR20","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1007\/BF02074876","volume":"32","author":"M. Hoshi","year":"1992","unstructured":"Hoshi, M., and Flajolet, P.: Page usage in a quadtree index.BIT,32 (1992), 384\u2013402.","journal-title":"BIT"},{"key":"BF01891833_CR21","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0065-2458(08)60257-0","volume":"27","author":"S. S. Iyengar","year":"1988","unstructured":"Iyengar, S. S., Rao, N. S. V., Kashyap, R. L., and Vaishnavi, V. K.: Multidimensional data structures: review and outlook.Advances in Computers,27 (1988), 69\u2013119.","journal-title":"Advances in Computers"},{"key":"BF01891833_CR22","volume-title":"vol. 3: Sorting and Searching","author":"D. E. Knuth","year":"1973","unstructured":"Knuth, D. E.The Art of Computer Programming, vol. 3: Sorting and Searching. Addison-Wesley, Reading, MA, 1973."},{"key":"BF01891833_CR23","volume-title":"Technical Report","author":"G. Labelle","year":"1991","unstructured":"Labelle, G., and Laforest, L. Variations combinatoires autour des arborescences hyperquaternaires. Technical Report, LACIM, UQAM, Montreal, Nov. 1991."},{"key":"BF01891833_CR24","volume-title":"Technical Report 3","author":"L. Laforest","year":"1990","unstructured":"Laforest, L. \u00c9tude des arbres hyperquaternaires. Technical Report 3, LACIM, UQAM, Montreal, Nov. 1990. (Author's Ph.D. thesis at McGill University.)"},{"issue":"4","key":"BF01891833_CR25","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1051\/ita\/1987210404791","volume":"21","author":"G. Louchard","year":"1987","unstructured":"Louchard, G.: Exact and asymptotic distributions in digital and binary search trees.RAIRO Theoretical Informatics and Applications,21(4) (1987), 479\u2013495.","journal-title":"RAIRO Theoretical Informatics and Applications"},{"key":"BF01891833_CR26","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0020-0190(87)90043-3","volume":"26","author":"C. Mathieu","year":"1987","unstructured":"Mathieu, C., Puech, C., and Yahia, H.: Average efficiency of data structures for binary image processing.Information Processing Letters,26 (Oct. 1987), 89\u201393.","journal-title":"Information Processing Letters"},{"key":"BF01891833_CR27","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/BF02189391","volume":"28","author":"A. M. Odlyzko","year":"1985","unstructured":"Odlyzko, A. M., and Richmond, L. B.: Asymptotic expansions for the coefficients of analytic generating functions.Aequationes Mathematicae,28 (1985), 50\u201363.","journal-title":"Aequationes Mathematicae"},{"key":"BF01891833_CR28","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry, An Introduction","author":"F. P. Preparata","year":"1985","unstructured":"Preparata, F. P., and Shamos, M. I.Computational Geometry, An Introduction. Springer-Verlag, New York, 1985."},{"key":"BF01891833_CR29","volume-title":"Doctorat \u00e9s sciences","author":"C. Puech","year":"1984","unstructured":"Puech, C.M\u00e9thodes d'analyse de structures de donn\u00e9es dynamiques. Doctorat \u00e9s sciences, Universit\u00e9 de Paris Sud, Orsay, 1984."},{"key":"BF01891833_CR30","doi-asserted-by":"crossref","unstructured":"Puech, C., and Yahia, H. Quadtrees, octrees, hyperoctrees: a unified approach to tree data structures used in graphics, geometric modeling and image processing.Proceedings of the First ACM Symposium on Computational Geometry, Baltimore, 1985, pp. 272\u2013280.","DOI":"10.1145\/323233.323268"},{"key":"BF01891833_CR31","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/BF01934379","volume":"25","author":"M. R\u00e9gnier","year":"1985","unstructured":"R\u00e9gnier, M.: Analysis of grid file algorithms.BIT,25 (1985), 335\u2013357.","journal-title":"BIT"},{"key":"BF01891833_CR32","unstructured":"Salvy, B. Asymptotique automatique et fonctions g\u00e9n\u00e9ratrices. Ph.D. thesis, \u00c9cole Polytechnique, 1991."},{"key":"BF01891833_CR33","volume-title":"The Design and Analysis of Spatial Data Structures","author":"H. Samet","year":"1990","unstructured":"Samet, H.The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, MA, 1990."},{"key":"BF01891833_CR34","volume-title":"Algorithms","author":"R. Sedgewick","year":"1988","unstructured":"Sedgewick, R.Algorithms, second edn. Addison-Wesley, Reading, MA, 1988.","edition":"second edn."},{"key":"BF01891833_CR35","volume-title":"Asymptotic Expansions for Ordinary Differential Equations","author":"W. Wasow","year":"1987","unstructured":"Wasow, W.Asymptotic Expansions for Ordinary Differential Equations. Dover, New York, 1987. A reprint of the Wiley edition, 1965."},{"key":"BF01891833_CR36","volume-title":"A Course of Modern Analysis","author":"E. T. Whittaker","year":"1927","unstructured":"Whittaker, E. T., and Watson, G. N.A Course of Modern Analysis, fourth edn. Cambridge University Press, Cambridge, 1927. Reprinted 1973.","edition":"fourth edn."},{"key":"BF01891833_CR37","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1016\/0022-247X(85)90209-4","volume":"111","author":"J. Wimp","year":"1985","unstructured":"Wimp, J., and Zeilberger, D.: Resurrecting the asymptotics of linear recurrences.Journal of Mathematical Analysis and Applications,111 (1985), 162\u2013176.","journal-title":"Journal of Mathematical Analysis and Applications"},{"key":"BF01891833_CR38","volume-title":"Doctorat de troisi\u00e9me cycle","author":"H. Yahia","year":"1986","unstructured":"Yahia, H. Analyse des structures de donn\u00e9es arborescentes repr\u00e9sentant des images. Doctorat de troisi\u00e9me cycle, Universit\u00e9 de Paris Sud, Orsay, Dec. 1986."},{"key":"BF01891833_CR39","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0377-0427(90)90042-X","volume":"32","author":"D. Zeilberger","year":"1990","unstructured":"Zeilberger, D.: A holonomic approach to special functions identities.Journal of Computational and Applied Mathematics,32 (1990), 321\u2013368.","journal-title":"Journal of Computational and Applied Mathematics"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01891833.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01891833\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01891833","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T00:22:24Z","timestamp":1586305344000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01891833"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,12]]},"references-count":39,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1993,12]]}},"alternative-id":["BF01891833"],"URL":"https:\/\/doi.org\/10.1007\/bf01891833","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,12]]}}}