A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-Off Algorithms
SCIE
SCOPUS
- Title
- A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-Off Algorithms
- Authors
- Oh, Eunjin; Ahn, Hee-Kap
- Date Issued
- 2019-07
- Publisher
- SPRINGER
- Abstract
- Given a read-only memory for input and a write-only stream for output, an s-workspace algorithm, for a positive integer parameter s, is an algorithm using only O(s) words of workspace in addition to the memory for the input. In this paper, we present an O(n2/s)-time s-workspace algorithm for subdividing a simple n-gon 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 by adopting the proposed subdivision: (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 problem (2) further by applying different approaches depending on the size of the workspace.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/100368
- DOI
- 10.1007/s00453-019-00558-9
- ISSN
- 0178-4617
- Article Type
- Article
- Citation
- ALGORITHMICA, vol. 81, no. 7, page. 2829 - 2856, 2019-07
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.