文章基本信息

标题：Time-Space Trade-offs for Triangulating a Simple Polygon
本地全文：下载
作者：Boris Aronov ; Matias Korman ; Simon Pratt 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：53
页码：30:1-30:12
DOI：10.4230/LIPIcs.SWAT.2016.30
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：simple polygon; triangulation; shortest path; time-space trade-off