University of Ljubljana, Faculty of Computer and Information Science and LUSY are hosting Robert Fraser from Sunday 27th until Monday 28th October 2013. Robert is currently a post-doc at University of Manitoba, Canada. His main research field is computational geometry.
You are kindly welcome to join us on Monday 28th October at 14:15 in PR-JA, Jadranska 21, when he will be having a talk titled Computational Geometry with Imprecise Data.
Abstract of the talk:
Data acquisition often has inherent imprecision, and there may also be imprecision introduced to data as a result of computation or other manipulation. We discuss the concept of solving computational geometry problems for which the input consists of a collection of sets (e.g. objects in the plane) rather than points, where a point must be selected from each set so as to optimize with respect to some objective function. We present the minimum spanning tree with neighborhoods problem, where the input is given as a set of disks, and the objective is to minimize or maximize the weight of the minimum spanning tree of the points selected from the disks. This example is of interest because it presents a study of one of the best-known computational geometry problems on one of the most natural and well-studied models of imprecision. We will examine properties that complicate attempts at finding exact solutions or even good approximations, and we will sketch why this model of imprecision causes the problem to become hard to approximate, even if the input disks are disjoint.