Campus Event Calendar
Event Entry
What and Who
A gap result for triangulations of finite point sets in the plane
Martin Kutz
Max-Planck-Institut für Informatik - D 1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 26 September 2006
13:30
30 Minutes
Warning: Date has changed!
E1 4
023
Saarbrücken
Warning: New Room!
Abstract
For a given finite set P of points in the plane, we want to construct a plane straight-line graph G that contains P as vertices such that detours in G (the ratio of G-distances between vertices and their Euklidian distance) are minimized. We show that with a few regular exceptions, for essentially no point set P the worst-case detour can be made arbitrarily small (close to 1). In other words, almost all point sets possess an intrinsic "rigidity" that makes it impossible to embed them in a geometric network with arbitrarily small (multiplicatively measured) detours.
This result was presented at this year's SoCG.
Contact
Martin Kutz
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Computational Geometry, Lower Bounds
Petra Mayer, 09/21/2006 15:14
Martin Kutz, 08/11/2006 14:40
Martin Kutz, 08/08/2006 13:16 -- Created document.
Martin Kutz, 08/11/2006 14:40
Martin Kutz, 08/08/2006 13:16 -- Created document.