## Summary

Our work solves the problem of how to place two watch towers in a region in *R*^{2}, such that the whole region can be seen from the top of the towers.

## Problem

Given a polyhedral region *T* in *R*^{2} with *n* corners. Find the minimum height *h* > 0, such that the watch tower with height *h* at the place of *u* and *v* cann see the entire region *T*.

## Solution

**Visibility pair computation:**

At first, describes how visiblity pairs on*T*are calculated:*P*is a given set of points from*T*and*V*is the set of vertices of*T*. We are looking for*v*∈*V*and a point*p*∈*P*(this must not necessarily exist), so that the following conditions are met:*p*is in the left of*v**p*sees*v**p*is the furthest right point with the conditions (i) and (ii) satisfied

*p*such that the segment*pv*has the biggest slope. Save all the points in an array.**Calculate visibility of the first tower:**

*H*is the region of the plane which is above*T*. In the decision procedure we find a vertex*u*∈*T*. Build the first Tower of height*h*at this point and calculate the visibility polygon*W*(*u*(*h*)), the part of*T*which can be seen from*u*(*h*). The part of*W*(*u*(*h*)) which lies on*T*consists of sections of edges of*T*or sections of visibility rays originating from*u*(*h*) which goes from a vertex of*T*. Let*P*= (*u, v*) be the set of end points of all*u*(*h*) from non-visible segments of*T*. Now it is clear that*u*(*h*) and a second tower*v*(*h'*), with possibly a different height*h'*, can completely overlook*T*, if*v*(*h'*) can see all points of*P*(*u, v*). Here it is enough to test the visibility at the corners of an edge, because if a point*v*(*h'*) over*T*can see both end points of a sub-segment, it will see the entire segment.**Determine the height of the second tower:**

Finally, we sweep from left to right through the plane using a vertical sweep line. We start at the*x*-coordinate of the leftmost vertex of*T*. We need a function*h*_{L}to calculate the miminum height of the tower at point*q*for each*q*∈*T*. This tower can watch all points of*P*which are on the left of the point*q*.*h*_{L}(*q*) corresponds to the distance between visible straight line of*q*and the upper contour*E*. The lowest distance between*T*and*E*is the height of the second tower, thus the whole problem is solved.