Computational geometry algorithms for visibility problems
Loading...
Files
Date
2019-09-18
Authors
Yeganeh, Bahoo Torudi
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis examines algorithmic problems involving k-crossing visibility. Given two points p and q and a set of polygonal obstacles in the plane, where p and q are in general position relative to the vertices of the obstacles, p and q are k -crossing visible to each other if and only if the line segment pq intersects obstacle boundaries in at most k points. Given a simple polygon P and a query point q, we show that region of P that is k-crossing visible from q can be calculated in O(nk), where n denotes number of vertices in P. With preprocessing of the polygon P, and using a data structure of size O(n^5), the k-crossing visible region for any query point q can be reported in O(log〖n+m〗) time, where m is the size of the output and q is given at query time.
When there is a constraint on the amount of memory available, the k-crossing visible region of q in P can be determined in O(cn/s+n log〖s 〗+min〖{[k/s]n,n loglog_sn }〗) time, where s denotes the number of words available in the limited workspace model. Finally, given an x-monotone polygonal chain, i.e., a terrain, we present an O(n^4 logn)-time algorithm to determine the minimum height of a watchtower point, located above the terrain, such that any point on the terrain is k-crossing visible from that point. Additionally, we propose an O(n^3)-time algorithm for the discrete version of the problem, in which the watchtower is restricted to being positioned over vertices of T.
Description
Keywords
Computational geometry, Visibility, Wireless system, k-crossing visibility, Decomposition, Watchtower problem