ANALYSIS OF THE WORST-CASE SPACE COMPLEXITY OF A PR QUADTREE

Authors
PEMMARAJU SV SHAFFER CA
Citation
Sv. Pemmaraju et Ca. Shaffer, ANALYSIS OF THE WORST-CASE SPACE COMPLEXITY OF A PR QUADTREE, Information processing letters, 49(5), 1994, pp. 263-267
Citations number
11
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
49
Issue
5
Year of publication
1994
Pages
263 - 267
Database
ISI
SICI code
0020-0190(1994)49:5<263:AOTWSC>2.0.ZU;2-#
Abstract
We demonstrate that a resolution-r PR quadtree containing n points has , in the worst case, at most 8n(r - [log4(n/2)]) + 8n/3 - 1/3 nodes. T his captures the fact that as n tends towards 4r, the number of nodes in a PR quadtree quickly approaches O(n). This is a more precise estim ation of the worst case space requirement of a PR quadtree then has be en attempted before.