petek, 7. marec 2014 Seminar MARA

V ponedeljek, 10. marca 2014, bo ob 16.00 uri v prostorih Fakultete za matematiko, naravoslovje in informacijske tehnologije Univerze na Primorskem, Glagoljaška 8, Koper predavanje v okviru skupnega SEMINARJA ZA MATEMATIČNE IN RAČUNALNIŠKE ZNANOSTI Oddelka za matematiko in Oddelka za Informacijske znanosti in tehnologije UP FAMNIT, Oddelka za matematiko in Oddelka za Informacijske znanosti in tehnologije UP IAM, Oddelka za matematiko in računalništvo UP PEF ter Oddelkov za matematiko in teoretično računalništvo IMFM.

RAČUNALNIŠKI SEMINAR

Prostor: FAMNIT-1-RU1 ob 16:00

Predavatelj: Daniela Maftuleac

Naslov: Shortest path problem in rectangular complexes of global non-positive curvature

Povzetek:
In this talk, we will present the results from the paper:
V. Chepoi and D. Maftuleac, Shortest path problem in rectangular complexes of global non-positive curvature,
Computational Geometry: Theory and Applications, 46 (2013), 51--64.

CAT(0) metric spaces (or metric spaces of global non-positive curvature) constitute a far-reaching common generalization of Euclidean and hyperbolic spaces and simple polygons: any two points x and y of a CAT(0) metric space are connected by a unique shortest path gamma(x, y).
In this talk, we present an efficient algorithm for answering two-point distance queries in CAT(0) rectangular complexes and two of theirs subclasses. Namely, we show that for a CAT(0) rectangular complex K with n vertices,
one can construct a data structure D of size O(n^2) so that, given any two points x, y in K, the shortest path
gamma(x, y) between x and y can be computed in O(d(p, q)) time, where p and q are vertices of two faces of K containing the points x and y, respectively, such that gamma(x, y) is contained in K(I(p, q)), d(p, q) is the distance between p and q in the underlying graph of K and I(p,q) is the interval between p and q in underlying graph of K.

Vabljeni!