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 with the
xy-plane. 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 a connection with the straight skeleton of
P. We show that the maximum possible number of distinct realistic roofs over
P is
(((n-4)/2) || (ë(n-4)/4û))(n-4)/2 \choose \lfloor(n-4)/4\rfloor when
P has
n vertices. We present an algorithm that enumerates a combinatorial representation of each such roof in
O(1) time per roof without repetition, after
O(
n
4) preprocessing time. We also present an
O(
n
5)-time algorithm for computing a realistic roof with minimum height or volume.
Work by Ahn was supported by the National Research Foundation of Korea Grant funded by the Korean Government (MEST) (NRF-2010-0009857).
Work by Bae and Lee was supported by National Research Foundation of Korea(NRF) grant funded by the Korea government(MEST)
(No. 2011-0005512). Work by Shin was Supported by research grant 2011 funded by Hankuk U. of Foreign Studies.