TR-95-09: Ray Shooting from Convex Ranges

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ne 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 ∈ X, is an edge if and only if the line joining pi to pj intersects 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.