n South African Computer Journal - Axial line placement in deformed urban grids : research article
|Article Title||Axial line placement in deformed urban grids : research article|
|© Publisher:||South African Computer Society (SAICSIT)|
|Journal||South African Computer Journal|
|Author||D. Wilkins and I. Sanders|
|Publication Date||Dec 2004|
|Pages||10 - 23|
|Keyword(s)||Axial lines, Computational geometry, Covering, F.2, F.2.2, G.2.1, G.2.2, Grids, Guarding, NP-complete problems, Space syntax, Town plans and Visibility|
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...