{"id":12774,"date":"2021-11-20T18:57:13","date_gmt":"2021-11-20T23:57:13","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12774"},"modified":"2021-11-20T18:57:13","modified_gmt":"2021-11-20T23:57:13","slug":"tr-95-09-ray-shooting-from-convex-ranges","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-09-ray-shooting-from-convex-ranges\/","title":{"rendered":"TR-95-09: Ray Shooting from Convex Ranges"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-95-09
\nApril 1995<\/p>\n

Ray Shooting from Convex Ranges<\/h2>\n
\n
\n
\n
\n
Evangelos Kranakis, Danny Krizanc, A. Maheshwari, J.R. Sack, J. Urrutia<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n
We consider geometric and graph-theoretic aspects of the well-known paradigm “killing two birds with one stone”. Consider that we have a set X of n-points in space and a compact plane convex set S. We defi\fne a graph G(X, S), called the ray shooting graph, on X as follows: The points of X are the vertices and {pi,pj} pi,pj\u00a0\u2208 X, is an edge if and only if the line joining pi\u00a0to pj\u00a0intersects S. Ray shooting graphs are shown to be comparability graphs, but the converse is shown not to be true. We provide a characterization of such graphs in terms of geometric containment orders and show that the recognition problem when S is a triangle is NP-complete.<\/div>\n

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

Carleton University Technical Report TR-95-09 April 1995 Ray Shooting from Convex Ranges Evangelos Kranakis, Danny Krizanc, A. Maheshwari, J.R. Sack, J. Urrutia Abstract We consider geometric and graph-theoretic aspects of the well-known paradigm “killing two birds with one stone”. Consider that we have a set X of n-points in space and a compact plane convex […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":11736,"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-95-09: Ray Shooting from Convex Ranges - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-95-09 April 1995 Ray Shooting from Convex Ranges Evangelos Kranakis, Danny Krizanc, A. Maheshwari, J.R. Sack, J.\" \/>\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-1995\/tr-95-09-ray-shooting-from-convex-ranges\/\" \/>\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-1995\/tr-95-09-ray-shooting-from-convex-ranges\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-09-ray-shooting-from-convex-ranges\/\",\"name\":\"TR-95-09: Ray Shooting from Convex Ranges - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-11-20T23:57:13+00:00\",\"dateModified\":\"2021-11-20T23:57:13+00:00\",\"description\":\"Carleton University Technical Report TR-95-09 April 1995 Ray Shooting from Convex Ranges Evangelos Kranakis, Danny Krizanc, A. Maheshwari, J.R. Sack, J.\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-09-ray-shooting-from-convex-ranges\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-09-ray-shooting-from-convex-ranges\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-09-ray-shooting-from-convex-ranges\/#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 1995\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-95-09: Ray Shooting from Convex Ranges\"}]},{\"@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-95-09: Ray Shooting from Convex Ranges - School of Computer Science","description":"Carleton University Technical Report TR-95-09 April 1995 Ray Shooting from Convex Ranges Evangelos Kranakis, Danny Krizanc, A. Maheshwari, J.R. Sack, J.","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-1995\/tr-95-09-ray-shooting-from-convex-ranges\/","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-1995\/tr-95-09-ray-shooting-from-convex-ranges\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-09-ray-shooting-from-convex-ranges\/","name":"TR-95-09: Ray Shooting from Convex Ranges - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-11-20T23:57:13+00:00","dateModified":"2021-11-20T23:57:13+00:00","description":"Carleton University Technical Report TR-95-09 April 1995 Ray Shooting from Convex Ranges Evangelos Kranakis, Danny Krizanc, A. Maheshwari, J.R. Sack, J.","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-09-ray-shooting-from-convex-ranges\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-09-ray-shooting-from-convex-ranges\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/tr-95-09-ray-shooting-from-convex-ranges\/#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 1995","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1995\/"},{"@type":"ListItem","position":5,"name":"TR-95-09: Ray Shooting from Convex Ranges"}]},{"@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\/12774"}],"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=12774"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12774\/revisions"}],"predecessor-version":[{"id":12775,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12774\/revisions\/12775"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11736"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12774"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}