|Mittagsseminar Talk Information|
Date and Time: Friday, January 05, 2007, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Boris Aronov (Department of Computer and Information Science, Polytechnic Univ., Brooklyn NY)
Sparse geometric graphs with small dilation
Given a set S of N points in R^2, and an integer K such that 0<=K<N,
we show that a geometric graph with vertex set S, at most N-1+K edges,
and dilation O(N/(K+1)) can be computed in time O(N log N). We also
construct N-point sets for which any geometric graph with N-1+K edges
has dilation Omega(N/(K+1)); a slightly weaker statement holds if the
points of S are required to be in convex position.
Higher dimensional analogues may also be discussed.
Here dilation of a straight-line Euclidean embedded graph is the
maximum ratio between the graph distance (the Euclidean length of the
shortest path) between a pair of its vertices to the Euclidean
distance between them.
Joint work with Mark de Berg, Otfried Cheong, Joachim Gudmundsson, Herman Haverkort,
Michiel Smid, and Antoine Vigneron.
Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)
Previous talks by year: 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
Information for students and suggested topics for student talks
Automatic MiSe System Software Version 1.3392 | admin login