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

No Thumbnail Available

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

Citation

Collections

Endorsement

Review

Supplemented By

Referenced By