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

Date, Time and Location

Tuesday, 26 September 2006
30 Minutes
E1 4


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.


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.