Finding Installation Sequence of Polygonal Masonry Through Design and Depth Search of a Directed Acyclic Graph

Abstract Polygonal masonry can be found in several historic buildings from various locations. There are several studies about the polygonal masonry techniques that are used during the construction of buildings: the wall of Inca Roca’s palace, Bomarsund fortress in Finland, and the fortress of Sacsayhuaman. However, when these polygonal stones are predesigned and the number of stones is substantial, it is hard to figure out the installation sequence due to the collisions between stones during the installation. This paper introduces an approach to solve this complicated problem by using a specific design method to define the shape of the polygonal stones, interpreting the relationship between the stones as a directed acyclic graph (DAG), and finding the depth of each node of this graph. The design of the stones is in ℝ2. The shapes of the stones are defined with the divided regions in ℝ2, divided by one or more functions and the boundary of the entire wall. Each stone is considered a node. The edges and directions of the graph are defined based on the character of adjacency between two regions. Depth search follows Kahn’s algorithm, but the algorithm searches in reversed order, removing the transitive reduction process of the graph. The conditions and assumptions about the design, collision, and graph are given in this paper.