View Related Documents

Abstract

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.

Fulltext Preview

Image of the first page of the fulltext document