First, suppose that a specific site and sequence of r reflecting walls are known. Then it is easy to compute a path consisting of r+1 line segments in three dimensions from transmitter to site. However, the walls intersected along the path must be determined to compute transmission loss coefficients. Naively, every wall in the building could be examined to see if it intersects the path, taking time proportional to nr. This time can be reduced by an appropriate spatial data structure.
The data structure is obtained using the observation that the number of distinct horizontal cross-sections of a building is small. Typically there is one cross-section for the floor, one for the space between floor and ceiling, and one for the ceiling (or if there is a false ceiling, one for it and one for the space between false and true ceilings). Each cross-section is two-dimensional and can be represented as a plane graph. The spatial data structure is just a triangulation of the graph, i.e., the addition of dummy line segments so that each bounded region is a triangle. To trace a path in three dimensions, it suffices to split it into subpaths lying within a single cross-section, and then within each cross-section trace the path projected into two dimensions. It is easy to do two-dimensional path tracing in time proportional to the number of intersected triangle line segments. On average, only about half the intersected line segments are added dummy line segments; the other half correspond to true wall intersections. Hence the total time for 3-d path tracing is approximately proportional to the actual number of walls intersected.
A second technique can reduce the number of wall sequences to be considered. Not every sequence of reflecting walls and sites determines a valid 3-d path. Consider a single wall W. The portion of three-dimensional space that can be illuminated from the transmitter by reflection off wall W is a truncated cone: the apex of the cone is the reflection R of the transmitter in the plane of W; the bounding planes of the cone are formed by R and the bounding edges of the wall W; the cone is truncated by deleting the portion of it on the same side of the plane through W as the apex R. Clearly, only sites within the truncated cone need to be considered for illumination by a one-reflection path off wall W. More generally, only walls that intersect the truncated cone need to be considered for two-reflection paths that start with wall W; such two-reflection paths illuminate similarly-defined truncated cones in 3-d.
The triangulation data structure can be used to report all walls that lie within a truncated cone in time roughly proportional to the number of reported walls. Similarly, a variant data structure reports all sites that lie within a truncated cone. The net effect is to vastly reduce the number of considered paths. However, the number of paths still grows exponentially, though with a base much smaller than n.
The two techniques produce a dramatic improvement in run-time. A two-reflection coverage map of Crawford Hill (n=80) reduced from 15 minutes to 45 seconds; a two-reflection coverage map of the NYSE (n=1500) reduced from an estimated 10 hours to 120 seconds. (These times are measured on an SGI system with a 40MHz R3000 processor.)
The predictor program is currently about 5800 lines of C++.