Realistic roofs over a rectilinear polygon

Heekap Ahn, Sangwon Bae, Christian Knauer, Mira Lee, Chansu Shin, Antoine E. Vigneron

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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.
Original languageEnglish (US)
Pages (from-to)1042-1055
Number of pages14
JournalComputational Geometry
Issue number9
StatePublished - Nov 2013

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Geometry and Topology
  • Computer Science Applications


Dive into the research topics of 'Realistic roofs over a rectilinear polygon'. Together they form a unique fingerprint.

Cite this