Memory-constrained algorithms for simple polygons

作者：Asano Tetsuo; Buchin Kevin; Buchin Maike; Korman Matias^*; Mulzer Wolfgang; Rote Guenter; Schulz Andre

来源：Computational Geometry-Theory and Applications, 2013, 46(8): 959-969.

DOI：10.1016/j.comgeo.2013.04.005

• Space-time trade-off
• Constant workspace
• Triangulation
• Shortest path
• Simple polygon

A constant-work-space algorithm has read-only access to an input array and may use only O(1) additional words of O(log n) bits, where n is the input size. We show how to triangulate a plane straight-line graph with n vertices in O(n(2)) time and constant work-space. We also consider the problem of preprocessing a simple polygon P for shortest path queries, where P is given by the ordered sequence of its n vertices. For this, we relax the space constraint to allow s words of work-space. After quadratic preprocessing, the shortest path between any two points inside P can be found in O(n(2)/s) time.

• 出版日期2013-10