2026-07-25T14:07:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6052 2024-03-06T10:37:32Z ddc:004 open_access

Time-Space Trade-offs for Triangulating a Simple Polygon Aronov, Boris Korman, Matias Pratt, Simon van Renssen, André Roeloffzen, Marcel simple polygon triangulation shortest path time-space trade-off 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 up to 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 up to n. In particular, the algorithm runs in O(n^2/s) expected time for most values of s. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Boris Aronov and Matias Korman and Simon Pratt and André van Renssen and Marcel Roeloffzen 2016 Is Part Of LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2016.30 urn:nbn:de:0030-drops-60522 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.30 eng https://creativecommons.org/licenses/by/3.0/legalcode