Largest bounding box, smallest diameter, and related problems on imprecise points

Imprecision of input data is one of the main obstacles that prevent geometric algorithms from being used in practice. We model an imprecise point by a region in which the point must lie. Given a set of imprecise points, we study computing the largest and smallest possible values of various basic geo...

Full description

Saved in:
Bibliographic Details
Published in:Computational geometry : theory and applications 2010-05, Vol.43 (4), p.419-433
Main Authors: Löffler, Maarten, van Kreveld, Marc
Format: Article
Language:English
Subjects:
Bounding box
Data imprecision
Diameter
Smallest enclosing circle
Width
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Imprecision of input data is one of the main obstacles that prevent geometric algorithms from being used in practice. We model an imprecise point by a region in which the point must lie. Given a set of imprecise points, we study computing the largest and smallest possible values of various basic geometric measures on point sets, such as the diameter, width, closest pair, smallest enclosing circle, and smallest enclosing bounding box. We give efficient algorithms for most of these problems, and identify the hardness of others.
ISSN:0925-7721
DOI:10.1016/j.comgeo.2009.03.007