Ponente: Leo Joskowicz (The Hebrew University of Jerusalem)
07/09/2010
de 12:00 a 13:00
Dónde Salón "Graciela Salicrup"
Classical computational geometrical algorithms handle geometric constructs whose shapes and locations are exact. However, many real-world applications require modeling and computing with geometric uncertainties, which are often coupled due to inaccuracies in sensing, measurement, and manufacturing processes. Most existing geometric models ignore the dependencies between the uncertainties, often overestimating the actual geometric error.
In this talk, we show how geometric uncertainty with dependencies is ubiquitous in many practical situations with examples from manufacturing, telecommunications, and surgery. We then present our recently developed Linear Parametric Geometric Uncertainty Model (LPGUM), a general and computationally efficient worst-case first-order linear approximation of geometric uncertainty that supports dependencies among uncertainties. We describe efficient algorithms for classical computational geometry problems, including relative position queries, point set distance problems, orthogonal range queries, convex hulls, and Voronoi diagrams in the presence of geometric uncertainty. We show that in nearly all cases, the overhead of computing with dependent uncertainties is low, and is thus practical.
Temas: