{"120221":{"#nid":"120221","#data":{"type":"event","title":"Prosenjit Bose, Carleton University, Canada","body":[{"value":"\u003Cp\u003ETitle: Competitive Routing on a Variant of the Delaunay Triangulation\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E A subgraph H of a weighted graph G is a t-spanner of G provided that for every edge xy in G, the weight of the shortest path between x and y in H is at most t times the weight of xy. It is known that the Delaunay triangulation of a point set P (where the empty region is an equilateral triangle) is a 2-spanner of the complete Euclidean graph. We present a new and simple proof of this spanning ratio that allows us to route competitively on this graph. Specifically, we present a deterministic local routing scheme that is guaranteed to find a short path between any pair of vertices in this Delaunay triangulation. We guarantee that the length of the path is at most 5\/sqrt(3) times the Euclidean distance between the pair of vertices. Moreover, we show that no local routing scheme can achieve a better competitive spanning ratio thereby implying that our routing scheme is optimal. This is somewhat surprising since the spanning ratio is 2.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Competitive Routing on a Variant of the Delaunay Triangulation"}],"uid":"27263","created_gmt":"2012-03-28 16:24:09","changed_gmt":"2016-10-08 01:58:33","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-04-05T18:30:00-04:00","event_time_end":"2012-04-05T18:30:00-04:00","event_time_end_last":"2012-04-05T18:30:00-04:00","gmt_time_start":"2012-04-05 22:30:00","gmt_time_end":"2012-04-05 22:30:00","gmt_time_end_last":"2012-04-05 22:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}