Od nedelje, 27. oktobra, do ponedeljka, 28. oktobra 2013, bo na Univerzi v Ljubljani, Fakulteti za računalništvo in informatiko gostoval Robert Fraser, podoktorski raziskovalec na Univerzi Manitoba, Kanada. Robert se ukvarja s področjem računske geometrije.
V ponedeljek, 28. oktobra ob 14:15 v PR-JA bo v sklopu FRI seminarja imel predavanje z naslovom Computational Geometry with Imprecise Data.
Povzetek predavanja v angleščini:
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.