n South African Computer Journal - Placing axial lines in urban grids
|Article Title||Placing axial lines in urban grids|
|© Publisher:||South African Computer Society (SAICSIT)|
|Journal||South African Computer Journal|
|Publication Date||Nov 2000|
|Pages||145 - 153|
|Keyword(s)||Also G.2.1, Also G.2.2, Axial lines, Computational geometry, Convex polygons, Covering, F.2, F.2.2, Grids, Guarding, NP-complete problems, Orthogonal rectangles, Town plans and Visibility|
In earlier papers the orthogonal axial line placement problem for orthogonal rectangles and the non-orthogonal axial line placement problem in orthogonal rectangles were presented. These problems were shown to be NP-Complete by transformations from the vertex cover problem for planar graphs. the general axial line placement problem - placing axial lines to cross the adjacencies between adjacent convex polygons - is a more general case of the problem of placing non-orthogonal axial lines in orthogonal rectangles and the NP-Completeness proof can be extended to this problem as well. In this paper the axial line placement problem and the related problem of generating the convex map for polygons with holes which can be represented as urban grids are considered. the paper shows that for these arrangements of polygons the solutions can be found in polynomial time. It is also conjectured that some more general configurations could also be solved in polynomial time.
Article metrics loading...