Computational geometry algorithms for visibility problems
| dc.contributor.author | Yeganeh, Bahoo Torudi | |
| dc.contributor.examiningcommittee | Evans, William (Computer Science, University of British Columbia), Kirkland, Stephen (Mathematics), Miller, Avery (Computer Science) | en_US |
| dc.contributor.supervisor | Durocher, Stephane (Computer Science), Bose, Prosenjit (Computer Science) | en_US |
| dc.date.accessioned | 2019-11-13T14:47:41Z | |
| dc.date.available | 2019-11-13T14:47:41Z | |
| dc.date.issued | 2019-09-18 | en_US |
| dc.date.submitted | 2019-09-18T17:16:53Z | en |
| dc.date.submitted | 2019-11-13T00:26:33Z | en |
| dc.degree.discipline | Computer Science | en_US |
| dc.degree.level | Doctor of Philosophy (Ph.D.) | en_US |
| dc.description.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. | en_US |
| dc.description.note | February 2020 | en_US |
| dc.identifier.uri | http://hdl.handle.net/1993/34366 | |
| dc.language.iso | eng | en_US |
| dc.rights | open access | en_US |
| dc.subject | Computational geometry | en_US |
| dc.subject | Visibility | en_US |
| dc.subject | Wireless system | en_US |
| dc.subject | k-crossing visibility | en_US |
| dc.subject | Decomposition | en_US |
| dc.subject | Watchtower problem | en_US |
| dc.title | Computational geometry algorithms for visibility problems | en_US |
| dc.type | doctoral thesis | en_US |