  When deciding where to place access points in a wireless network, it is
useful to model the signal propagation loss between a proposed antenna location
and the areas it may cover. The indoor dominant path (IDP) model, introduced by
W\"{o}lfle et al., is shown in the literature to have good validation and
generalization error, is faster to compute than competing methods, and is used
in commercial software such as WinProp, iBwave Design, and CellTrace.
Previously, the algorithms known for computing it involved a worst-case
exponential-time tree search, with pruning heuristics to speed it up.
  We prove that the IDP model can be reduced to a parametric shortest path
computation on a graph derived from the walls in the floorplan. It therefore
admits a quasipolynomial-time (i.e., $n^{O(\log n)}$) algorithm. We also give a
practical approximation algorithm based on running a small constant number of
shortest path computations. Its provable worst-case additive error (in dB) can
be made arbitrarily small via appropriate choices of parameters, and is well
below 1dB for reasonable choices. We evaluate our approximation algorithm
empirically against the exact IDP model, and show that it consistently beats
its theoretical worst-case bounds, solving the model exactly (i.e., no error)
in the vast majority of cases.
