TR-239: Killing Two Birds with One Stone

Abstract

We consider geometric and graph-theoretic applications of the well-known paradigm “killing two birds with one stone”. In the plane, this gives rise to a stage graph as follows: vertices are the points, and { u, v} is an edge if and only if the (infinite, straight) line segment joining u to v intersects the stage. We give algorithms for “optimal” ray shootings of a collection of points in the plane from a given stage, including a characterization of stage graphs in time O(n2 ), and show how to recognize all dominances in O(log n) time using 0( n + k / log n) processors on the EREW PRAM, where k is the total number of dominances. Similar problems occur when we have a fixed number k of stages on the plane. In this case, { u, v} is an edge if and only if the (straight) line segment uv intersects one of the k stages. We consider the problem of constructing stage representations of arbitrary graphs and give upper and lower bounds on the number of stages thus required. We also study the 3-dimensional case. This gives rise to 3 ray shooting graphs; these are formed from a set of points in IR.3 and a “stage” which is a compact plane convex set. 3 ray shooting graphs are shown to be comparability graphs, but the converse is shown not to be true. We also provide a characterization of such graphs in terms of