| Popis: |
We consider visibility problems on a terrain. Given two stations located at different points on the terrain, we would like to find the minimum heights of communication towers at the two locations so that they can communicate freely. Formally, given two points q 1 and q 2 on the terrain, we would to find the height h 1 and h 2 such that if one lift q i up by h i , for i = 1, 2, the lifted points see each other with the minimum cost that depends linearly on h 1 and h 2 . We consider two versions of the problem. When given two points q 1 and q 2 on a terrain with n vertices, with the preprocessing time of O(n log n), we can answer the query in time O(log n + d) where d is the number of terrain edges between q 1 and q 2 . When one point q 1 is fixed, given q 2 and e > 0, we can give an approximate answer with additive error at most e in time O(log2 (h max /e) · log n) where h max is the maximum height in terrain. In this case, the preprocessing time is O(n 2 ). |
