Meulemans, W. & Haunert, JH. (2016). Partitioning Polygons via Graph Augmentation. Lecture Notes in Computer Science, 9927, pp. 1833. doi: 10.1007/9783319457383

Text
 Accepted Version
Download (656kB)  Preview 
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 graphbased 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 lineartime 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 NPhard. Finally, we show how our algorithm can be used for two wellknown problems in GIS: generating variablescale maps and area aggregation.
Item Type:  Article 

Additional Information:  The final publication is available at Springer via http://dx.doi.org/10.1007/9783319457383 
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