2018
A time–space trade-off for computing the k-visibility region of a point in a polygon
Publication
Publication
Let P be a simple polygon with n vertices, and let q∈P be a point in P. Let k∈{0,…,n−1}. A point p∈P is k-visible from q if and only if the line segment pq crosses the boundary of P at most k times. The k-visibility region of q in P is the set of all points that are k-visible from q. We study the problem of computing the k-visibility region in the limited workspace model, where the input resides in a random-access read-only memory of O(n) words, each with Ω(logn) bits. The algorithm can read and write O(s) additional words of workspace, where s∈N is a parameter of the model. The output is written to a write-only stream. Given a simple polygon P with n vertices and a point q∈P, we present an algorithm that reports the k-visibility region of q in P in O(cn/s+clogs+min{⌈k/s⌉n,nloglogsn}) expected time using O(s) words of workspace. Here, c∈{1,…,n} is the number of critical vertices of P for q where the k-visibility region of q may change. We generalize this result for polygons with holes and for sets of non-crossing line segments.
Additional Metadata | |
---|---|
, , | |
doi.org/10.1016/j.tcs.2018.06.017 | |
Theoretical Computer Science | |
Organisation | School of Computer Science |
Bahoo, Y. (Yeganeh), Banyassady, B. (Bahareh), Bose, P, Durocher, S. (Stephane), & Mulzer, W. (Wolfgang). (2018). A time–space trade-off for computing the k-visibility region of a point in a polygon. Theoretical Computer Science. doi:10.1016/j.tcs.2018.06.017
|