{"id":13181,"date":"2021-12-07T20:24:18","date_gmt":"2021-12-08T01:24:18","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13181"},"modified":"2021-12-07T20:24:18","modified_gmt":"2021-12-08T01:24:18","slug":"tr-06-13-distribution-sensitive-point-location-in-convex-subdivisions","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2006\/tr-06-13-distribution-sensitive-point-location-in-convex-subdivisions\/","title":{"rendered":"TR-06-13: Distribution-Sensitive Point Location in Convex Subdivisions"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-06-13
\nNovember 27, 2006<\/p>\n

Distribution-Sensitive Point Location in Convex Subdivisions<\/h2>\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

Sebastien Collette, John Iacono, Stefan Langerman, Pat Morin<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\n

Abstract<\/h3>\n

A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is within a constant factor of optimal.<\/p>\n

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

Carleton University Technical Report TR-06-13 November 27, 2006 Distribution-Sensitive Point Location in Convex Subdivisions Sebastien Collette, John Iacono, Stefan Langerman, Pat Morin Abstract A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is within […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":12352,"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-06-13: Distribution-Sensitive Point Location in Convex Subdivisions - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-06-13 November 27, 2006 Distribution-Sensitive Point Location in Convex Subdivisions Sebastien Collette, John\" \/>\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-2006\/tr-06-13-distribution-sensitive-point-location-in-convex-subdivisions\/\" \/>\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-2006\/tr-06-13-distribution-sensitive-point-location-in-convex-subdivisions\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2006\/tr-06-13-distribution-sensitive-point-location-in-convex-subdivisions\/\",\"name\":\"TR-06-13: Distribution-Sensitive Point Location in Convex Subdivisions - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-12-08T01:24:18+00:00\",\"dateModified\":\"2021-12-08T01:24:18+00:00\",\"description\":\"Carleton University Technical Report TR-06-13 November 27, 2006 Distribution-Sensitive Point Location in Convex Subdivisions Sebastien Collette, John\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2006\/tr-06-13-distribution-sensitive-point-location-in-convex-subdivisions\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2006\/tr-06-13-distribution-sensitive-point-location-in-convex-subdivisions\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2006\/tr-06-13-distribution-sensitive-point-location-in-convex-subdivisions\/#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 2006\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2006\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-06-13: Distribution-Sensitive Point Location in Convex Subdivisions\"}]},{\"@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-06-13: Distribution-Sensitive Point Location in Convex Subdivisions - School of Computer Science","description":"Carleton University Technical Report TR-06-13 November 27, 2006 Distribution-Sensitive Point Location in Convex Subdivisions Sebastien Collette, John","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-2006\/tr-06-13-distribution-sensitive-point-location-in-convex-subdivisions\/","schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2006\/tr-06-13-distribution-sensitive-point-location-in-convex-subdivisions\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2006\/tr-06-13-distribution-sensitive-point-location-in-convex-subdivisions\/","name":"TR-06-13: Distribution-Sensitive Point Location in Convex Subdivisions - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-12-08T01:24:18+00:00","dateModified":"2021-12-08T01:24:18+00:00","description":"Carleton University Technical Report TR-06-13 November 27, 2006 Distribution-Sensitive Point Location in Convex Subdivisions Sebastien Collette, John","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2006\/tr-06-13-distribution-sensitive-point-location-in-convex-subdivisions\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2006\/tr-06-13-distribution-sensitive-point-location-in-convex-subdivisions\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2006\/tr-06-13-distribution-sensitive-point-location-in-convex-subdivisions\/#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 2006","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2006\/"},{"@type":"ListItem","position":5,"name":"TR-06-13: Distribution-Sensitive Point Location in Convex Subdivisions"}]},{"@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\/13181"}],"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=13181"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13181\/revisions"}],"predecessor-version":[{"id":13182,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13181\/revisions\/13182"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12352"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13181"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}