アイテムの簡略レコードを表示する

Approximate Range Searching: The Absolute Model

dc.contributor.authorda Fonseca, Guilherme D.
dc.contributor.authorMount, David M.
dc.date.accessioned2007-07-02T17:47:49Z
dc.date.available2007-07-02T17:47:49Z
dc.date.issued2007-05-07
dc.identifier.urihttp://hdl.handle.net/1903/7037
dc.description.abstractRange searching is a well known problem in the area of geometric data structures. 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 case of relative errors, 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 consider a different approximation model, called the absolute 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 range spaces consisting of halfspaces, Euclidean balls, simplices, axis-aligned rectangles, and general convex bodies. We consider a variety of problem formulations, including range searching under general commutative semigroups, idempotent semigroups, groups, and range emptiness. We show how idempotence can be used to improve not only approximate, but also exact halfspace range searching. Our data structures are much simpler than both their exact and relative model counterparts, and so are amenable to efficient implementation.en
dc.format.extent213992 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_USen
dc.relation.ispartofseriesUM Computer Science Departmenten
dc.relation.ispartofseriesCS-TR-4873en
dc.titleApproximate Range Searching: The Absolute Modelen
dc.typeTechnical Reporten


このアイテムのファイル

Thumbnail

このアイテムは次のコレクションに所属しています

アイテムの簡略レコードを表示する