Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

- Lars Arge
- Jakob Truelsen, Denmark
- Jungwoo Yang, Denmark

We present the first I/O- and practically-efficient algorithm for simplifying a planar subdivision, such that no point is moved more than a given distance εxy and such that neighbor relations between faces (homotopy) are preserved. Under some practically realistic assumptions, our algorithm uses (SORT(N)) I/Os, where N is the size of the decomposition and SORT(N) is the number of I/Os need to sort in the standard external-memory model of computation. Previously, such an algorithm was only known for the special case of contour map simplification.

Our algorithm is simple enough to be of practical interest. In fact, although more general, it is significantly simpler than the previous contour map simplification algorithm. We have implemented our algorithm and present results of experimenting with it on massive real-life data. The experiments confirm that the algorithm is efficient in practice. For example, for the contour map simplification problem it is significantly faster than the previous algorithm, while obtaining approximately the same simplification factor.

Read More: http://epubs.siam.org/doi/abs/10.1137/1.9781611973198.3

Our algorithm is simple enough to be of practical interest. In fact, although more general, it is significantly simpler than the previous contour map simplification algorithm. We have implemented our algorithm and present results of experimenting with it on massive real-life data. The experiments confirm that the algorithm is efficient in practice. For example, for the contour map simplification problem it is significantly faster than the previous algorithm, while obtaining approximately the same simplification factor.

Read More: http://epubs.siam.org/doi/abs/10.1137/1.9781611973198.3

Original language | English |
---|---|

Title of host publication | 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX) |

Editors | Catherine C. McGeoch, Ulrich Meyer |

Number of pages | 11 |

Publisher | Society for Industrial and Applied Mathematics |

Publication year | 2014 |

Pages | 20-30 |

ISBN (Electronic) | 978-1-61197-319-8 |

DOIs | |

Publication status | Published - 2014 |

Event | Workshop on Algorithm Engineering and Experiments - Portland, United States Duration: 5 Jan 2014 → 5 Jan 2014 Conference number: 16 |

Workshop | Workshop on Algorithm Engineering and Experiments |
---|---|

Nummer | 16 |

Land | United States |

By | Portland |

Periode | 05/01/2014 → 05/01/2014 |

See relations at Aarhus University Citationformats

ID: 69097892