[English] [Sitemap] [Über geometrylab.de]
	Startseite > Algorithmische Geometrie > Verschiedenes > Watchtower

Summary

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

Problem

Given a polyhedral region T in R² 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

1. 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:
   1. p is in the left of v
   2. p sees v
   3. p is the furthest right point with the conditions (i) and (ii) satisfied
   Alternative: From the points that satisfy (i) and (ii) search a point p such that the segment pv has the biggest slope. Save all the points in an array.
2. 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.
3. 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.

© Universität Bonn, Informatik Abt. I - - Letzte Änderung 27-05-2009 01:44