Return to search

A greedy heuristic for axial line placement in collections of convex polygons

Master of Science - Science / Axial line placement is one step in a method known as space syntax which is used in town
planning to analyse architectural structures. This is becoming increasingly important in the
quickly growing urban world of today. The field of axial line placement is an area of space
syntax that has previously been done manually which is becoming increasingly impractical.

Research is underway to automate the process and this research forms a large part of the automation.
The general problem of axial line placement has been shown to be NP-complete. For this reason, previous research in this field has been focused on finding special cases where this is not the case or finding heuristics that approximate a solution.
The majority of the research conducted has been on the simpler case of axial line placement in configurations of orthogonal rectangles and the only work done with convex polygons has been in the restricted case of deformed urban grids. This document presents research that finds two non-trivial special cases of convex polygons that have polynomial solutions and finds the first heuristic for general configurations of convex polygons.

Identiferoai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:wits/oai:wiredspace.wits.ac.za:10539/194
Date15 February 2006
CreatorsHagger, Leonard
Source SetsSouth African National ETD Portal
LanguageEnglish
Detected LanguageEnglish
TypeThesis
Format837740 bytes, application/pdf, application/pdf

Page generated in 0.0014 seconds