Analysis of the Worst Case Space Complexity of a PR Quadtree

Files

TR-92-09.pdf (346.52 KB)
Downloads: 881

TR Number

TR-92-09

Date

1992

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Department of Computer Science, Virginia Polytechnic Institute & State University

Abstract

We demonstrate that a resolution-r PR quadtree containing n points has, in the worst case, at most nodes. This 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 estimation of the worst case space requirement of a PR quadtree than has been attempted before.

Description

Keywords

Citation

Persistent link

http://hdl.handle.net/10919/19649

Collections

Computer Science Technical Reports