Meulemans, W. & Haunert, J-H. (2016).
Partitioning Polygons via Graph Augmentation.
*Lecture Notes in Computer Science*, 9927,
pp. 18-33.
doi: 10.1007/978-3-319-45738-3

Text
- Accepted Version
Restricted to Repository staff only until 14 September 2017. Download (656kB) | Request a copy |

## Abstract

We study graph augmentation under the dilation criterion. In our case, we consider a plane geometric graph G = (V, E) and a set C of edges. We aim to add to G a minimal number of nonintersecting edges from C to bound the ratio between the graph-based distance and the Euclidean distance for all pairs of vertices described by C. Motivated by the problem of decomposing a polygon into natural subregions, we present an optimal linear-time algorithm for the case that P is a simple polygon and C models an internal triangulation of P. The algorithm admits some straightforward extensions. Most importantly, in pseudopolynomial time, it can approximate a solution of minimum total length or, if C is weighted, compute a solution of minimum total weight. We show that minimizing the total length or the total weight is weakly NP-hard. Finally, we show how our algorithm can be used for two well-known problems in GIS: generating variable-scale maps and area aggregation.

Item Type: | Article |
---|---|

Additional Information: | The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-45738-3 |

Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |

Divisions: | School of Informatics > giCentre |

URI: | http://openaccess.city.ac.uk/id/eprint/15169 |

### Actions (login required)

View Item |

### Downloads

Downloads per month over past year