TY - GEN

T1 - Generating realistic roofs over a rectilinear polygon

AU - Ahn, Heekap

AU - Bae, Sangwon

AU - Knauer, Christian

AU - Lee, Mira

AU - Shin, Chansu

AU - Vigneron, Antoine E.

N1 - KAUST Repository Item: Exported on 2020-10-01

PY - 2011

Y1 - 2011

N2 - 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)/4⌋ (n-4)/2) 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. © 2011 Springer-Verlag.

AB - 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)/4⌋ (n-4)/2) 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. © 2011 Springer-Verlag.

UR - http://hdl.handle.net/10754/564348

UR - http://link.springer.com/10.1007/978-3-642-25591-5_8

UR - http://www.scopus.com/inward/record.url?scp=84055184939&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-25591-5_8

DO - 10.1007/978-3-642-25591-5_8

M3 - Conference contribution

SN - 9783642255908

SP - 60

EP - 69

BT - Lecture Notes in Computer Science

PB - Springer Nature

ER -