Realistic roofs over a rectilinear polygon
SCIE
SCOPUS
- Title
- Realistic roofs over a rectilinear polygon
- Authors
- Ahn, HK; Bae, SW; Knauer, C; Lee, M; Shin, CS; Vigneron, A
- Date Issued
- 2013-11
- Publisher
- ELSEVIER SCIENCE BV
- 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 pi/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 left perpendicular(n-4)/4right perpendicular) 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. (C) 2013 Elsevier B.V. All rights reserved.
- Keywords
- Realistic roof; Straight skeleton; Rectilinear polygon; Enumeration algorithm; MOTORCYCLE GRAPHS
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/14841
- DOI
- 10.1016/J.COMGEO.2013.06.002
- ISSN
- 0925-7721
- Article Type
- Article
- Citation
- COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, vol. 46, no. 9, page. 1042 - 1055, 2013-11
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.