|
|||||
|
|
Guarding a Terrain by Two Watchtowers |
|
| Authors: | Pankaj K. Agarwal Sergey Bereg Ovidiu Daescu Haim Kaplan Simeon Ntafos Micha Sharir Binhai Zhu |
| Affiliation: | 1. Department of Computer Science, Duke University, Durham, NC, 27708, USA 2. Department of Computer Science, University of Texas at Dallas, Box 830688, Richardson, TX, 75083, USA 3. School of Computer Science, Tel Aviv University, Tel Aviv, 69978, Israel 4. Courant Institute of Mathematical Sciences, New York University, New York, NY, 10012, USA 5. Department of Computer Science, Montana State University, Bozeman, MT, 59717-3880, USA |
| Abstract: | 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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |