Activity‎ > ‎

2011. 12. 22 GAIA Seminar: Generating Realistic Roofs over a Rectilinear Polygon

posted Dec 21, 2011, 4:48 PM by dongwoo park   [ updated Dec 26, 2011, 6:06 PM by Soomin Jung ]
Title: Generating 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 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 choose (n-4)/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: Hee-Kap Ahn (GAIA & POSTECH)