Single-crossing orthogonal axial lines in orthogonal rectangles
No Thumbnail Available
Date
2008-06-30T07:58:31Z
Authors
Mengisteab, Berhane Semere
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
Keywords
axial lines, computational geometry, NP-complete, domination sets