Analysis of the worst case space complexity of a PR quadtree

Sriram V Pemmaraju; Clifford A Shaffer

doi:10.1016/0020-0190(94)90065-5

Back

Analysis of the worst case space complexity of a PR quadtree

Journal article

Open access

Peer reviewed

Analysis of the worst case space complexity of a PR quadtree

Sriram V Pemmaraju and Clifford A Shaffer

Information processing letters, Vol.49(5), pp.263-267

1994

DOI: 10.1016/0020-0190(94)90065-5

Files and links (1)

url

https://doi.org/10.1016/0020-0190(94)90065-5View

Published (Version of record) Open Access

Abstract

We domonstrate that a resolution- r PR quadtree containing n points has, in the worst case, at most 8n(r− [log 4( n 2 ]) + 8n 3 − 1 3 nodes. This captures the fact that as n tends towards 4 r , 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 then has been attempted before.

Data structures

Point data

PR quadtree

Spacial data structures

Worst case analysis

Details

Title: Subtitle: Analysis of the worst case space complexity of a PR quadtree
Creators: Sriram V Pemmaraju - Virginia Tech
Clifford A Shaffer - Virginia Tech
Resource Type: Journal article
Publication Details: Information processing letters, Vol.49(5), pp.263-267
DOI: 10.1016/0020-0190(94)90065-5
ISSN: 0020-0190
eISSN: 1872-6119
Publisher: Elsevier B.V
Language: English
Date published: 1994
Academic Unit: Computer Science
Record Identifier: 9984259461402771

Metrics

25 Record Views

5 Times Cited - Web of Science