Campus Event Calendar
Event Entry
What and Who
PhD Application Talk: Approximation of the Minimum Spanning Tree of Set of Points in the Hausdorff Metric.
Victor Alvarez
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, RG2
MPI Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 29 October 2007
08:00
90 Minutes
E1 4
024
Saarbrücken
Abstract
Let P be a set of points in a d-dimensional space and let 0< e < 1 a given parameter. We will show that is not possible in general to find a subset Q' of P of size independent of |P| such that: |MST(Q')| >= (1 - e)|MST(P)|. Where |MST(P)| denotes the weight of the euclidean minimum spanning tree of P. On the positive side, we will show the existence of a subset Q of P such that its size is independent of the size of P and such that a spanning tree ST(Q) and MST(P) are close in the Hausdorff metric, that is, they look essentially equal. This might have applications in Image Comparison, Pattern Recognition and actually gives a way to compress MST(P) as the space required to store ST(Q) is independent of |P|. Further, we also give possible approaches to compute such a spanning tree ST(Q) and therefore Q under any given fixed metric Lp, 1 <= p <= infty, and any fixed dimension d.
Contact
IMPRS
-225
--email hidden
passcode not visible
logged in users only
Lourdes Lara-Tapia, 10/26/2007 19:02 -- Created document.