City Research Online

Partitioning Polygons via Graph Augmentation

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

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.

Publication 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
Departments: School of Science & Technology > Computer Science > giCentre
SWORD Depositor:
[thumbnail of gisciencesubmission.pdf]
Preview
Text - Accepted Version
Download (656kB) | Preview

Export

Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login