n South African Computer Journal - A greedy heuristic for Axial Line Placement in collections of convex polygons : reviewed article
|Article Title||A greedy heuristic for Axial Line Placement in collections of convex polygons : reviewed article|
|© Publisher:||South African Computer Society (SAICSIT)|
|Journal||South African Computer Journal|
|Author||L. Hagger and I.D. Sanders|
|Publication Date||Dec 2006|
|Pages||51 - 60|
|Keyword(s)||Axial lines, computational geometry, Convex polygons, Covering, Guarding, NP-complete problems and Visibility|
The Axial Line Placement problem has been shown to be NP-complete. This means that work into finding approximate solutions to the general problem is warranted. The majority of the research conducted so far has concentrated on the restricted case of axial line placement in collections of orthogonal rectangles. The only work done with convex polygons has been in the restricted case of deformed urban grids. This article presents the first heuristic for placing axial lines in collections of adjacent non-overlapping convex polygons.
Article metrics loading...