Abstract
We study graph augmentation under the dilation criterion. In our case, we consider a plane geometric graph G=(V,E)
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.
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.
| Original language | English |
|---|---|
| Title of host publication | Geographic Information Science |
| Subtitle of host publication | 9th International Conference, GIScience 2016, Montreal, QC, Canada, September 27-30, 2016, Proceedings |
| Editors | J.A. Miller, D. O'Sullivan, N. Wiegand |
| Place of Publication | Dordrecht |
| Publisher | Springer |
| Pages | 18-33 |
| ISBN (Electronic) | 978-3-319-45738-3 |
| ISBN (Print) | 978-3-319-45737-6 |
| DOIs | |
| Publication status | Published - 2016 |
| Externally published | Yes |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Volume | 9927 |