TY - JOUR

T1 - 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
Acknowledgements: 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 was supported by National Research Foundation of Korea (NRF) grant funded by the Korean Government (MEST) (No. 2011-0005512). Work by Shin was supported by research grant funded by Hankuk University of Foreign Studies.

PY - 2013/11

Y1 - 2013/11

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. According to this definition, some roofs may have faces isolated from the boundary of P or even local minima, which are undesirable for several practical reasons. 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 that the straight skeleton induces a realistic roof with maximum height and volume. We also show that the maximum possible number of distinct realistic roofs over P is ((n-4)(n-4)/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(n4) preprocessing time. We also present an O(n5)-time algorithm for computing a realistic roof with minimum height or volume. © 2013 Elsevier B.V.

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. According to this definition, some roofs may have faces isolated from the boundary of P or even local minima, which are undesirable for several practical reasons. 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 that the straight skeleton induces a realistic roof with maximum height and volume. We also show that the maximum possible number of distinct realistic roofs over P is ((n-4)(n-4)/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(n4) preprocessing time. We also present an O(n5)-time algorithm for computing a realistic roof with minimum height or volume. © 2013 Elsevier B.V.

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

UR - https://linkinghub.elsevier.com/retrieve/pii/S0925772113000801

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

U2 - 10.1016/j.comgeo.2013.06.002

DO - 10.1016/j.comgeo.2013.06.002

M3 - Article

SN - 0925-7721

VL - 46

SP - 1042

EP - 1055

JO - Computational Geometry

JF - Computational Geometry

IS - 9

ER -