کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
415414 | 681207 | 2013 | 14 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Realistic roofs over a rectilinear polygon Realistic roofs over a rectilinear polygon](/preview/png/415414.png)
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π/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)/2⌊(n−4)/4⌋) when P has n vertices. We present an algorithm that enumerates a combinatorial representation of each such roof in O(1)O(1) time per roof without repetition, after O(n4)O(n4) preprocessing time. We also present an O(n5)O(n5)-time algorithm for computing a realistic roof with minimum height or volume.
Journal: Computational Geometry - Volume 46, Issue 9, November 2013, Pages 1042–1055