UNAM
You are here: Home / Actividades académicas / Coloquios / Coloquio de Ciudad Universitaria / Actividades del Coloquio / Uncertain geometry with dependencies

Uncertain geometry with dependencies

Leo Joskowicz (The Hebrew University of Jerusalem)
Ponente: Leo Joskowicz (The Hebrew University of Jerusalem)

When Sep 07, 2010
from 12:00 PM to 01:00 PM
Where Salón "Graciela Salicrup"
Add event to calendar vCal
iCal

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.

Filed under: