The University of Arizona

Events & News

CS Colloquium

DateThursday, December 4, 2014
Time11:00 am
Concludes12:15 pm
LocationGould-Simpson 906
DetailsPlease join us for coffee and light refresments at 11am in Gould-Simpson 906.

Faculty Host: John Hartman
SpeakerWill Evans
TitleAssociate Professor
AffiliationDepartment of Computer Science, University of British Columbia

Competitive Query Strategies for Minimising Ply of the Potential Locations of Moving Parts

Data in motion presents challenges for algorithms whose output depends on the location of the data. The challenges arise when the motion is unpredictable and we are unable or unwilling to maintain exact knowledge of the location of the data. We consider a model where the current location of at most one object (among many) may be obtained in each time step and the objects have limited speed. This means that
the future position of an object whose location is known now lies in a bounded uncertainty region. We address the question of which objects we should query in what order to obtain the least confusing knowledge of the collection of objects. Our measure of confusion is the maximum number of uncertainty regions that overlap - the ply of the regions. We describe a strategy that without knowledge of the future trajectories of the objects can decide which objects to query so that the ply of the regions is at most a constant times the ply obtainable by an all-knowing query strategy.


Will Evans received a PhD in computer science at UC Berkeley in 1994, was a postdoc at the University of British Columbia for two years, and an assistant professor at the University of Arizona until 2000. Since then he's been at UBC. He's interested in algorithmic and geometric aspects of computer science as well as compression, especially of program representations.