The Axial line placement problem

Show simple item record

dc.contributor.advisor Kourie, Derrick G. en
dc.contributor.postgraduate Sanders, Ian Douglas en
dc.date.accessioned 2013-09-07T14:03:33Z
dc.date.available 2005-10-17 en
dc.date.available 2013-09-07T14:03:33Z
dc.date.created 2002-09-01 en
dc.date.issued 2005-10-17 en
dc.date.submitted 2005-10-13 en
dc.description Thesis (DPhil (Computer Science))--University of Pretoria, 2005. en
dc.description.abstract Visibility, guarding and polygon decomposition are problems in the field of compu¬tational geometry which have roots in real world applications. These problems have been the focus of much research over a number of years. This thesis introduces a new problem in the field - The Axial line Placement Problem - which has some commonalities with these other problems. The problem arises from a consideration of the computational issues that result from attempting to automate the space syntax method. Space syntax is used for describing, quantifying and interpreting the spatial patterns in urban designs by analysing the relationship between the space through which one can move (roads, parks, etc.) and the buildings in the urban layout. In particular, this thesis considers the problem of the placing the axial lines, defining paths along which someone can move, to cross the shared boundaries between the convex polygons which represent the space through which someone can move in the town. A number of simplifications of the original problem are considered in this thesis. The first of these is the problem of placing the smallest number of orthogonal line segments (orthogonal axial lines) to cross the shared boundaries (adjacencies) in a collection of adjacent orthogonal rectangles. This problem is shown to be NP¬Complete by a transformation from the vertex cover problem for planar graphs. A heuristic algorithm which produces an approximation to the general solution is then presented. In addition, special cases of collections of orthogonal rectangles which allow polynomial time solutions are described and algorithms to solve some ofthese special cases are presented. The problem where the axial lines, that pass through the adjacencies between or¬thogonal rectangles, can have arbitrary orientation is then considered. This problem is also shown to be NP-Complete and once again heuristic approaches to solving the problem are considered. The problem of placing axial lines to cross the adjacencies between adjacent convex polygons is a more general case of the problem of placing axial lines of arbitrary orientation in orthogonal rectangles. The NP-Completeness proof can be extended to this problem as well. The final stage of the thesis considers real world urban layouts. Many urban layouts are regular grids of roads. Such layouts can be modelled as general urban grids and this thesis shows that it is possible to find the minimal axial line cover in general urban grids in polynomial time. Some urban layouts are less regular and the idea of a deformed urban grid is introduced to model some of these layouts. A heuristic algorithm that finds a partition of a deformed urban grid in polynomial time is presented and it is conjectured that the axial map of a deformed urban grid can be found in polynomial time. The problem is still open for more general urban layouts which cannot be modelled by deformed urban grids. The contribution of this thesis is that a number of new NP-Complete problems were identified and some new and interesting problems in the area of computational geometry have been introduced. en
dc.description.availability unrestricted en
dc.description.department Computer Science en
dc.identifier.citation Sanders, ID 2002, The axial line placement problem, DPhil thesis, University of Pretoria, Pretoria, viewed yymmdd < http://hdl.handle.net/2263/28673 > en
dc.identifier.other H1159/ag en
dc.identifier.upetdurl http://upetd.up.ac.za/thesis/available/etd-10132005-094604/ en
dc.identifier.uri http://hdl.handle.net/2263/28673
dc.language.iso en
dc.publisher University of Pretoria en_ZA
dc.rights © 2002 University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria. en
dc.subject Computational grids computer science en
dc.subject Architecture computer aided design en
dc.subject UCTD en_US
dc.title The Axial line placement problem en
dc.type Thesis en


Files in this item

This item appears in the following Collection(s)

Show simple item record