Consider a set X of n-points in space, each with positive z-coordinate, and a compact plane convex set S. We define 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 infinite line joining pi to pj intersects S. In this paper we provide a characterization of shooting graphs; they are exactly the set of comparability graphs of containment orders arising from families of plane homothetic convex sets. We also prove that the crossing number of these ordered sets is at most 2, and that not all comparability graphs are three-dimensional ray-shooting graphs.

Additional Metadata
Keywords 68R10, 68U05, Geometric containment, Partial orders, Ray shooting graphs
Persistent URL dx.doi.org/10.1016/S0166-218X(00)00180-3
Journal Discrete Applied Mathematics
Citation
Kranakis, E, Krizanc, D. (Danny), Maheshwari, A, Sack, J.-R, & Urrutia, J. (Jorge). (2001). Ray shooting from convex ranges. Discrete Applied Mathematics, 108(3), 259–267. doi:10.1016/S0166-218X(00)00180-3