Realistic roofs over a rectilinear polygon ?
Given a simple rectilinear polygon P in the xy-plane, a roof over P is a terrain over P whose faces are supported by planes through edges of P  that make a dihedral angle ?/4 ? / 4 with the xy-plane. According to this definition, some roofs may have faces isolated from the boundary of P or even local minima, which are undesirable for several practical reasons. In this paper, we introduce realistic roofs by imposing a few additional constraints. We investigate the geometric and combinatorial properties of realistic roofs and show that the straight skeleton induces a realistic roof with maximum height and volume. We also show that the maximum possible number of distinct realistic roofs over P  is ( ( n ? 4 ) / 2 ? ( n ? 4 ) / 4 ? ) when P has n  vertices. We present an algorithm that enumerates a combinatorial representation of each such roof in O(1) O ( 1 ) time per roof without repetition, after O(n4) O ( n 4 ) preprocessing time. We also present an O(n5) O ( n 5 ) -time algorithm for computing a realistic roof with minimum height or volume.
realistic roof rectilinear polygon straight skeleton enumeration algorithm