Analysis of the Worst Case Space Complexity of a PR Quadtree

Simple item page
dc.contributor.authorPemmaraju, Sriram V.en
dc.contributor.authorShaffer, Clifford A.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2013-06-19T14:36:00Zen
dc.date.available2013-06-19T14:36:00Zen
dc.date.issued1992en
dc.description.abstractWe 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.en
dc.format.mimetypeapplication/pdfen
dc.identifierhttp://eprints.cs.vt.edu/archive/00000289/en
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000289/01/TR-92-09.pdfen
dc.identifier.trnumberTR-92-09en
dc.identifier.urihttp://hdl.handle.net/10919/19649en
dc.language.isoenen
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen
dc.relation.ispartofHistorical Collection(Till Dec 2001)en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.titleAnalysis of the Worst Case Space Complexity of a PR Quadtreeen
dc.typeTechnical reporten
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR-92-09.pdf
Size:
346.52 KB
Format:
Adobe Portable Document Format
Download

Collections

Computer Science Technical Reports