We are given a read-only memory for input and a write-only stream for output. For a positive integer parameter s, an s-workspace algorithm is an algorithm using only O(s) words of workspace in addition to the memory for input. In this paper, we present an O(n^2/s)-time s-workspace algorithm for subdividing a simple polygon into O(min{n/s,s}) subpolygons of complexity O(max{n/s,s}). As applications of the subdivision, the previously best known time-space trade-offs for the following three geometric problems are improved immediately: (1) computing the shortest path between two points inside a simple n-gon, (2) computing the shortest path tree from a point inside a simple n-gon, (3) computing a triangulation of a simple n-gon. In addition, we improve the algorithm for the second problem even further.
展开▼
机译：我们为输入提供了一个只读存储器，为输出提供了一个只写流。对于正整数参数s，s工作空间算法是一种算法，除了用于输入的内存外，仅使用工作空间的O（s）个字。在本文中，我们提出了一种O（n ^ 2 / s）时间s-workspace算法，用于将简单多边形细分为复杂度为O（ max {的O（ min {n / s，s }））个子多边形n / s，s }）。作为该细分的应用，以下三个几何问题的先前最著名的时空折衷得到了立即改善：（1）计算简单n形内两个点之间的最短路径，（2）计算最短路径从简单n角内的点开始的树，（3）计算简单n角的三角剖分。另外，我们进一步改进了第二个问题的算法。
展开▼
