Realistic roofs without local minimum edges over a rectilinear polygon

Computing all possible roofs over a given ground plan is a common task in automatically reconstructing a three dimensional building. In 1995, Aichholzer et al. proposed a definition of a roof over a simple polygon P in the xy-plane as a terrain over P whose faces are supported by planes containing edges of P and making a dihedral angle π/4 with the xy-plane. This definition, however, allows roofs with faces isolated from the boundary of P and local minimum edges inducing pools of rainwater. Very recently, Ahn et al. introduced “realistic roofs” over a rectilinear polygon with n vertices by imposing two additional constraints under which no isolated faces and no local minimum vertices are allowed. Their definition is, however, restricted and excludes a number of roofs with no local minimum edges. In this paper, we propose a new definition of realistic roofs over a rectilinear polygon that corresponds to the class of roofs without isolated faces and local minimum edges. We investigate the geometric and combinatorial properties of realistic roofs and show that the maximum possible number of distinct realistic roofs over a rectilinear n-gon is at most 1.3211m(m⌊m/2⌋), where m=(n−4)/2. We also present two algorithms that generate all realistic roofs.