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

keywords: Computational Geometry, Data Imprecision

### Journal Article (peer-reviewed)

Maarten Löffler, Marc van Kreveld

Largest Bounding Box, Smallest Diameter, and Related Problems on Imprecise Points

Computational Geometry: Theory and Applications

43, 4, 419–433, 2010

### Conference Proceedings (peer-reviewed)

Maarten Löffler, Marc van Kreveld

Largest Bounding Box, Smallest Diameter, and Related Problems on Imprecise Points

Proc. 10th Workshop on Algorithms and Data Structures

LNCS 4619, 447–458, 2007

*Invited to Special Issue of CGTA*

### Technical Report (not reviewed)

Maarten Löffler, Marc van Kreveld

Largest Bounding Box, Smallest Diameter, and Related Problems on Imprecise Points

UU-CS-2007-025, 2007

back to list