We study the problem of computing the k-visibility region in the memory-constrained model. In this model, the input resides in a randomly accessible read-only memory of O(n) words, with O(log n) bits each. An algorithm can read and write O(s) additional words of workspace during its execution, and it writes its output to write-only memory. In a given polygon P and for a given point q ∈ P, we say that a point p is inside the k-visibility region of q, if and only if the line segment pq intersects the boundary of P at most k times. Given a simple n-vertex polygon P stored in a read-only input array and a point q ∈ P, we give a time-space trade-off algorithm which reports the kvisibility region of q in P in O(cn/s+n log s+min{⌈k/s⌉n, n log logs n}) expected time using O(s) words of workspace. Here c ≤ n is the number of critical vertices for q, i.e., the vertices of P where the visibility region may change. We also show how to generalize this result for polygons with holes and for sets of non-crossing line segments.

Additional Metadata
Keywords K-visibility region, Memory-constrained model, Timespace trade-off
Persistent URL dx.doi.org/10.1007/978-3-319-53925-6_24
Series Lecture Notes in Computer Science
Citation
Bahoo, Y. (Yeganeh), Banyassady, B. (Bahareh), Bose, P, Durocher, S. (Stephane), & Mulzer, W. (Wolfgang). (2017). Time-space trade-off for finding the K-visibility region of a point in a polygon. In Lecture Notes in Computer Science. doi:10.1007/978-3-319-53925-6_24