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 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.

slides

Journal Article (peer-reviewed)

Conference Proceedings (peer-reviewed)

Technical Report (not reviewed)

back to list