Approximate Range Searching In The Absolute Error Model

Simple item page
dc.contributor.advisorMount, David Men_US
dc.contributor.authorFonseca, Guilherme Dias daen_US
dc.contributor.departmentComputer Scienceen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2008-04-22T16:07:40Z
dc.date.available2008-04-22T16:07:40Z
dc.date.issued2007-11-28en_US
dc.description.abstractRange searching is a well known problem in computational geometry. We consider this problem in the context of approximation, where an approximation parameter eps > 0 is provided. Most prior work on this problem has focused on the relative error model, where each range shape R is bounded, and points within distance eps diam(R) of the range's boundary may or may not be included. We introduce a different approximation model, called the absolute error model, in which points within distance eps of the range's boundary may or may not be included, regardless of the diameter of the range. We consider sets of ranges consisting of general convex bodies, axis-aligned rectangles, halfspaces, Euclidean balls, and simplices. We examine a variety of problem formulations, including range searching under general commutative semigroups, idempotent semigroups, groups, range emptiness, and range reporting. We apply our data structures to several related problems, including range sketching, approximate nearest neighbor searching, exact idempotent range searching, approximate range searching in the data stream model, and approximate range searching in the relative model.en_US
dc.format.extent866362 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/7770
dc.language.isoen_US
dc.subject.pqcontrolledComputer Scienceen_US
dc.subject.pqcontrolledComputer Scienceen_US
dc.subject.pquncontrolledcomputational geometryen_US
dc.subject.pquncontrolleddata structuresen_US
dc.subject.pquncontrolledrange searchingen_US
dc.subject.pquncontrolledgeometric approximationen_US
dc.titleApproximate Range Searching In The Absolute Error Modelen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
umi-umd-5052.pdf
Size:
846.06 KB
Format:
Adobe Portable Document Format
Download

Collections

UMD Theses and Dissertations
Computer Science Theses and Dissertations