The Axial line placement problem

Abstract

Visibility, guarding and polygon decomposition are problems in the field of compu¬tational geometry which have roots in real world applications. These problems have been the focus of much research over a number of years. This thesis introduces a new problem in the field - The Axial line Placement Problem - which has some commonalities with these other problems. The problem arises from a consideration of the computational issues that result from attempting to automate the space syntax method. Space syntax is used for describing, quantifying and interpreting the spatial patterns in urban designs by analysing the relationship between the space through which one can move (roads, parks, etc.) and the buildings in the urban layout. In particular, this thesis considers the problem of the placing the axial lines, defining paths along which someone can move, to cross the shared boundaries between the convex polygons which represent the space through which someone can move in the town. A number of simplifications of the original problem are considered in this thesis. The first of these is the problem of placing the smallest number of orthogonal line segments (orthogonal axial lines) to cross the shared boundaries (adjacencies) in a collection of adjacent orthogonal rectangles. This problem is shown to be NP¬Complete by a transformation from the vertex cover problem for planar graphs. A heuristic algorithm which produces an approximation to the general solution is then presented. In addition, special cases of collections of orthogonal rectangles which allow polynomial time solutions are described and algorithms to solve some ofthese special cases are presented. The problem where the axial lines, that pass through the adjacencies between or¬thogonal rectangles, can have arbitrary orientation is then considered. This problem is also shown to be NP-Complete and once again heuristic approaches to solving the problem are considered. The problem of placing axial lines to cross the adjacencies between adjacent convex polygons is a more general case of the problem of placing axial lines of arbitrary orientation in orthogonal rectangles. The NP-Completeness proof can be extended to this problem as well. The final stage of the thesis considers real world urban layouts. Many urban layouts are regular grids of roads. Such layouts can be modelled as general urban grids and this thesis shows that it is possible to find the minimal axial line cover in general urban grids in polynomial time. Some urban layouts are less regular and the idea of a deformed urban grid is introduced to model some of these layouts. A heuristic algorithm that finds a partition of a deformed urban grid in polynomial time is presented and it is conjectured that the axial map of a deformed urban grid can be found in polynomial time. The problem is still open for more general urban layouts which cannot be modelled by deformed urban grids. The contribution of this thesis is that a number of new NP-Complete problems were identified and some new and interesting problems in the area of computational geometry have been introduced.