The axial map of a town is one of the key components of the space syntax method – a tool
for analysing urban layout. It is derived by placing the longest and fewest lines, called axial
lines, to cross the adjacencies between convex polygons in a convex map of a town. Previous
research has shown that placing axial lines to cross the adjacencies between a collection of
convex polygons is NP-complete, even when the convex polygons are restricted to rectangles
and the axial lines to have orthogonal orientation.
In this document, we show that placing orthogonal axial lines in orthogonal rectangles
where the adjacencies between the rectangles are restricted to be crossed only once (ALPSC-
OLOR) is NP-complete. As a result, we infer the single adjacency crossing version
of the general axial line placement problem is NP-complete. The transformation of NPcompleteness
of ALP-SC-OLOR is from vertex cover for biconnected planar graphs. A
heuristic is then presented that gives a reasonable approximate solution to ALP-SC-OLOR
based on a greedy method.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:wits/oai:wiredspace.wits.ac.za:10539/4994 |
| Date | 30 June 2008 |
| Creators | Mengisteab, Berhane Semere |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 674167 bytes, application/pdf, application/pdf |
Page generated in 0.0243 seconds