Title: Generating Realistic Roofs over a Rectilinear Polygon Abstract Given a simple rectilinear polygon P in the xyplane, 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 xyplane. 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 (n4)/2 choose (n4)/4 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. ▶Speaker: Sang Won Bae (Kyonggi Univ)
▷Organizer: HeeKap Ahn (GAIA & POSTECH)

Activity >