n South African Computer Journal - Axial line placement in deformed urban grids : research article




Axial line placement is a computational geometry problem with direct applications to Space Syntax Analysis, a technique used in the analysis of building and city layouts. While it has been shown that the general axial line placement problem is NP-complete, polynomial time solutions have been found for several restricted versions of the problem. Of these, the case of urban grids is the most applicable to space syntax. Urban grids are polygons that can be used to represent some real-world layouts, but are relatively restricted in their modelling power. The concept of a deformed urban grid was therefore introduced in an attempt to find a more flexible structure, while retaining the grid-like nature of urban grids. It was originally conjectured that this restricted nature of deformed urban grids would allow for an exact polynomial time solution of the problem. However, this article presents a proof showing that the axial line placement problem for deformed urban grids is NP-complete. As this result holds for grids with relatively little deformation, it seems likely that urban grids are the most general input instance for which exact polynomial time solutions can be found. The development of good heuristic solutions to more general instances of the problem will therefore be crucial in the automation of space syntax.


Article metrics loading...

This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error