Show simple item record

dc.contributor.authorLattanzi, Mark R.en_US
dc.date.accessioned2014-03-14T21:42:03Z
dc.date.available2014-03-14T21:42:03Z
dc.date.issued1989-05-15en_US
dc.identifier.otheretd-08012012-040610en_US
dc.identifier.urihttp://hdl.handle.net/10919/44120
dc.description.abstractTwo 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.mediumBTDen_US
dc.publisherVirginia Techen_US
dc.relation.haspartLD5655.V855_1989.L377.pdfen_US
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectTrees (Graph theory)en_US
dc.subject.lccLD5655.V855 1989.L377en_US
dc.titleTable-driven quadtree traversal algorithmsen_US
dc.typeThesisen_US
dc.contributor.departmentComputer Science and Applicationsen_US
dc.description.degreeMaster of Scienceen_US
thesis.degree.nameMaster of Scienceen_US
thesis.degree.levelmastersen_US
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen_US
thesis.degree.disciplineComputer Science and Applicationsen_US
dc.contributor.committeechairShaffer, Clifford A.en_US
dc.contributor.committeememberArthur, James D.en_US
dc.contributor.committeememberHeath, Lenwood S.en_US
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-08012012-040610/en_US
dc.date.sdate2012-08-01en_US
dc.date.rdate2012-08-01
dc.date.adate2012-08-01en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record