Go to  Advanced Search

Guarantees concerning geometric objects with imprecise points

Show full item record

Files in this item

Files Size Format Description   View
ubc_2011_fall_sember_jeff.pdf 1.536Mb Adobe Portable Document Format   View/Open
Title: Guarantees concerning geometric objects with imprecise points
Author: Sember, Jeffery
Degree Doctor of Philosophy - PhD
Program Computer Science
Copyright Date: 2011
Publicly Available in cIRcle 2011-10-19
Abstract: Traditional geometric algorithms are often presented as if input imprecision does not exist, even though it is often unavoidable. We argue that in some cases, it may be desirable for geometric algorithms to treat this imprecision as an explicit component of the input, and to reflect this imprecision in the output. Starting with three problems from computational geometry whose inputs are planar point sets (Voronoi diagrams, convex hulls, and smallest bounding discs), we recast these as problems where each input point's location is imprecise, but known to lie within a particular region of uncertainty. Where algorithms to solve each of the original problems produce a single geometric object as output, the algorithms that we present typically produce either guaranteed or possible output objects. A guaranteed object represents qualities that can be guaranteed for every point set that is consistent with the uncertain regions, and a possible object represents qualities that exist for at least one such point set. By dealing with input imprecision explicitly, these guaranteed and possible objects can represent a more accurate view of what can be reliably inferred from the input data.
URI: http://hdl.handle.net/2429/38084
Scholarly Level: Graduate

This item appears in the following Collection(s)

Show full item record

All items in cIRcle are protected by copyright, with all rights reserved.

UBC Library
1961 East Mall
Vancouver, B.C.
Canada V6T 1Z1
Tel: 604-822-6375
Fax: 604-822-3893