A greedy heuristic for axial line placement in collections of convex polygons
Date
2006-02-15
Authors
Hagger, Leonard
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
Master of Science - Science
Keywords
heuristic, axial line, greedy, convex, polygons