dc.contributor.author Lattanzi, Mark R. en_US dc.date.accessioned 2014-03-14T21:42:03Z dc.date.available 2014-03-14T21:42:03Z dc.date.issued 1989-05-15 en_US dc.identifier.other etd-08012012-040610 en_US dc.identifier.uri http://hdl.handle.net/10919/44120 dc.description.abstract Two quadtree algorithms are presented that use table driven traversals to reduce the time complexity required to achieve their respective goals. The first algorithm is a two step process that converts a boundary representation of a polygon into a corresponding region representation of the same image. The first step orders the border pixels of the polygon. The second step fills in the polygon in O(B) time where B is the number of border pixels for the polygon of interest. A table propagates the correct values of upcoming nodes in a simulated traversal of the final region quadtree. This is unique because the pointer representation of the tree being traversed does not exist. A linear quadtree representation is constructed as this traversal proceeds. The second algorithm is an update algorithm for a quadtree (or octtree) of moving particles. Particle simulations have had the long-standing problem of calculating the interactions among n particles. It takes O(n2) time for direct computation of all the interactions between n particles. Greengard [Gree87, Carr87] has devised a way to approximate these calculations in linear time using a tree data structure. However, the particle simulation must still rebuild the particle tree after every iteration, which requires O(n log n) time. Our algorithm updates the existing tree of particles, rather than building a new tree. It operates in near linear time in the number of particles being simulated. The update algorithm uses a table to store particles as they move between nodes of the tree. en_US dc.format.medium BTD en_US dc.publisher Virginia Tech en_US dc.relation.haspart LD5655.V855_1989.L377.pdf en_US dc.rights In Copyright en dc.rights.uri http://rightsstatements.org/vocab/InC/1.0/ en dc.subject Trees (Graph theory) en_US dc.subject.lcc LD5655.V855 1989.L377 en_US dc.title Table-driven quadtree traversal algorithms en_US dc.type Thesis en_US dc.contributor.department Computer Science and Applications en_US dc.description.degree Master of Science en_US thesis.degree.name Master of Science en_US thesis.degree.level masters en_US thesis.degree.grantor Virginia Polytechnic Institute and State University en_US thesis.degree.discipline Computer Science and Applications en_US dc.contributor.committeechair Shaffer, Clifford A. en_US dc.contributor.committeemember Arthur, James D. en_US dc.contributor.committeemember Heath, Lenwood S. en_US dc.identifier.sourceurl http://scholar.lib.vt.edu/theses/available/etd-08012012-040610/ en_US dc.date.sdate 2012-08-01 en_US dc.date.rdate 2012-08-01 dc.date.adate 2012-08-01 en_US
﻿