Time-space trade-offs for triangulating a simple polygon

Boris Aronov, Matias Korman, Simon Pratt, André Van Renssen, Marcel Roeloffzen

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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(n2/s + n(log s) log5 (n/s)) expected time using O(s) variables, for any s ∈ O(n). In particular, when s ∈ O(n/log n log5 log n) algorithm runs in O(n2/s) expected time.

    Original languageEnglish (US)
    Title of host publication15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016
    EditorsRasmus Pagh
    PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
    Pages30.1-30.12
    ISBN (Electronic)9783959770118
    DOIs
    StatePublished - Jun 1 2016
    Event15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016 - Reykjavik, Iceland
    Duration: Jun 22 2016Jun 24 2016

    Publication series

    NameLeibniz International Proceedings in Informatics, LIPIcs
    Volume53
    ISSN (Print)1868-8969

    Other

    Other15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016
    CountryIceland
    CityReykjavik
    Period6/22/166/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