### Abstract

An s-workspace algorithm is an algorithm that has read-only access to the values of the input, write-only access to the output, and only uses O(s) additional words of space. We give a randomized s-workspace algorithm for triangulating a simple polygon P of n vertices, for any s ∈ O(n). The algorithm runs in O(n^{2}/s + n(log s) log^{5} (n/s)) expected time using O(s) variables, for any s ∈ O(n). In particular, when s ∈ O(n/log n log^{5} log n) algorithm runs in O(n^{2}/s) expected time.

Original language | English (US) |
---|---|

Title of host publication | 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016 |

Editors | Rasmus Pagh |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Pages | 30.1-30.12 |

ISBN (Electronic) | 9783959770118 |

DOIs | |

State | Published - Jun 1 2016 |

Event | 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016 - Reykjavik, Iceland Duration: Jun 22 2016 → Jun 24 2016 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 53 |

ISSN (Print) | 1868-8969 |

### Other

Other | 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016 |
---|---|

Country | Iceland |

City | Reykjavik |

Period | 6/22/16 → 6/24/16 |

### Keywords

- Shortest path
- Simple polygon
- Time-space trade-off
- Triangulation

### ASJC Scopus subject areas

- Software

## Cite this

Aronov, B., Korman, M., Pratt, S., Van Renssen, A., & Roeloffzen, M. (2016). Time-space trade-offs for triangulating a simple polygon. In R. Pagh (Ed.),

*15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016*(pp. 30.1-30.12). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 53). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.SWAT.2016.30