{"id":13120,"date":"2021-12-06T18:45:47","date_gmt":"2021-12-06T23:45:47","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13120"},"modified":"2021-12-06T18:45:47","modified_gmt":"2021-12-06T23:45:47","slug":"tr-04-08-approximate-distance-oracles-for-geometric-spanners","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2004\/tr-04-08-approximate-distance-oracles-for-geometric-spanners\/","title":{"rendered":"TR-04-08: Approximate Distance Oracles for Geometric Spanners"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-04-08
\nOctober 2004<\/p>\n

Approximate Distance Oracles for Geometric Spanners<\/h2>\n
\n
\n
\n
\n
\n
\n
\n
\n
\n
Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, Michiel Smid<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n

Given an arbitrary real constant $\\eps > 0$, and a geometric graph $G$ in $d$-dimensional Euclidean space with $n$ points, $m$ edges, and constant dilation, we present a data structure that answers $(1+\\eps)$-approximate shortest path length queries in constant time. The data structure can be constructed in $O(m + n \\log n)$ time using $O(n\\log n)$ space. This represents the first data structure that answers $(1+\\eps)$-approximate shortest path queries in constant time, and hence functions as an approximate distance oracle. The data structure is also applied to several other problems. In particular, we also show that approximate shortest path queries between vertices in a planar polygonal domain with “rounded” obstacles can be answered in constant time. Other applications include query versions of closest pair problems, and the efficient computation of the approximate dilations of geometric graphs.<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

TR-04-08.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-04-08 October 2004 Approximate Distance Oracles for Geometric Spanners Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, Michiel Smid Abstract Given an arbitrary real constant $\\eps > 0$, and a geometric graph $G$ in $d$-dimensional Euclidean space with $n$ points, $m$ edges, and constant dilation, we present a data structure that answers $(1+\\eps)$-approximate […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":12325,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"yoast_head":"\nTR-04-08: Approximate Distance Oracles for Geometric Spanners - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-04-08 October 2004 Approximate Distance Oracles for Geometric Spanners Joachim Gudmundsson, Christos Levcopoulos,\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2004\/tr-04-08-approximate-distance-oracles-for-geometric-spanners\/\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2004\/tr-04-08-approximate-distance-oracles-for-geometric-spanners\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2004\/tr-04-08-approximate-distance-oracles-for-geometric-spanners\/\",\"name\":\"TR-04-08: Approximate Distance Oracles for Geometric Spanners - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-12-06T23:45:47+00:00\",\"dateModified\":\"2021-12-06T23:45:47+00:00\",\"description\":\"Carleton University Technical Report TR-04-08 October 2004 Approximate Distance Oracles for Geometric Spanners Joachim Gudmundsson, Christos Levcopoulos,\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2004\/tr-04-08-approximate-distance-oracles-for-geometric-spanners\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2004\/tr-04-08-approximate-distance-oracles-for-geometric-spanners\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2004\/tr-04-08-approximate-distance-oracles-for-geometric-spanners\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/carleton.ca\/scs\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Research\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"SCS Technical Reports\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Technical Reports 2004\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2004\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-04-08: Approximate Distance Oracles for Geometric Spanners\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/carleton.ca\/scs\/#website\",\"url\":\"https:\/\/carleton.ca\/scs\/\",\"name\":\"School of Computer Science\",\"description\":\"Carleton University\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/carleton.ca\/scs\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"TR-04-08: Approximate Distance Oracles for Geometric Spanners - School of Computer Science","description":"Carleton University Technical Report TR-04-08 October 2004 Approximate Distance Oracles for Geometric Spanners Joachim Gudmundsson, Christos Levcopoulos,","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2004\/tr-04-08-approximate-distance-oracles-for-geometric-spanners\/","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2004\/tr-04-08-approximate-distance-oracles-for-geometric-spanners\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2004\/tr-04-08-approximate-distance-oracles-for-geometric-spanners\/","name":"TR-04-08: Approximate Distance Oracles for Geometric Spanners - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-12-06T23:45:47+00:00","dateModified":"2021-12-06T23:45:47+00:00","description":"Carleton University Technical Report TR-04-08 October 2004 Approximate Distance Oracles for Geometric Spanners Joachim Gudmundsson, Christos Levcopoulos,","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2004\/tr-04-08-approximate-distance-oracles-for-geometric-spanners\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2004\/tr-04-08-approximate-distance-oracles-for-geometric-spanners\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2004\/tr-04-08-approximate-distance-oracles-for-geometric-spanners\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/carleton.ca\/scs\/"},{"@type":"ListItem","position":2,"name":"Research","item":"https:\/\/carleton.ca\/scs\/research\/"},{"@type":"ListItem","position":3,"name":"SCS Technical Reports","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/"},{"@type":"ListItem","position":4,"name":"Technical Reports 2004","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2004\/"},{"@type":"ListItem","position":5,"name":"TR-04-08: Approximate Distance Oracles for Geometric Spanners"}]},{"@type":"WebSite","@id":"https:\/\/carleton.ca\/scs\/#website","url":"https:\/\/carleton.ca\/scs\/","name":"School of Computer Science","description":"Carleton University","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/carleton.ca\/scs\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"}]}},"acf":{"banner_image_type":"none","banner_button":"no"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13120"}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/49"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=13120"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13120\/revisions"}],"predecessor-version":[{"id":13121,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13120\/revisions\/13121"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12325"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13120"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}