# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

__Mittagsseminar Talk Information__ | |

**Date and Time**: Tuesday, April 20, 2004, 12:15 pm

**Duration**: This information is not available in the database

**Location**: This information is not available in the database

**Speaker**: Michael Hoffmann (2) (University of Leicester)

## Efficient Update Strategies for Geometric Computing with Uncertainty

We consider the problems of computing maximal points and the
convex hull of a set of points in 2D, when the points are
``in motion.'' We assume that the point locations (or trajectories)
are not known precisely and determining these values exactly is
feasible, but expensive. In our model, the algorithm only knows
areas within which each of the input points lie, and is required
to identify the maximal points or points on the convex hull correctly
by updating some points (i.e. determining exactly their location).
We compare the number of points updated by the algorithm on a given
instance to the minimum number of points that must be updated by a
nondeterministic strategy in order to provably compute the answer
correctly. We give algorithms for both of the above problems that
always update at most 3 times as many points as the nondeterministic
strategy, and show that this is the best possible.

(Joint work with Rajeev Raman and Danny Krizanc)

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login