Abstract: Motivated by the inaccuracy of GPS-based location devices in urban regions, we study the problem of computing the visibility graph of an urban region. Given a scene of buildings, where a building is represented by the set of its walls, the vertices of the graph correspond to the buildings' walls, and there is an edge between two walls if and only if they are \emph{weakly} visible to each other. We present efficient algorithms for several scenes, including a sophisticated $O(n^2 \log^2 n)$-time algorithm for a scene consisting of $n$ parallel walls of varying heights, which uses persistent search trees in a non-standard manner.