Guarding a Terrain by Two Watchtowers

摘要

Given a polyhedral terrain T with n vertices, the two-watchtower problem for T asks to find two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases) lie on T, and whose top endpoints guard T, in the sense that each point on T is visible from at least one of them. There are three versions of the problem, discrete, semi-continuous, and continuous, depending on whether two, one, or none of the two bases are restricted to be among the vertices of T, respectively.