سیویلیکا را در شبکه های اجتماعی دنبال نمایید.

Guarding a Terrain by a Single k-modem Watchtower

Publish Year: 1390
Type: Conference paper
Language: English
View: 1,989

This Paper With 6 Page And PDF Format Ready To Download

Export:

Link to this Paper:

Document National Code:

CSCCIT01_192

Index date: 28 January 2012

Guarding a Terrain by a Single k-modem Watchtower abstract

In this paper we study the problem of guarding a 2-dimentional terrain by the shortest k-modem watchtower, for a given constant k. We refer to a 2-dimentional terrain as an x-monotone polygonal chain. A kmodem watchtower is a vertical segment whose lower endpoint lies on the terrain and the upper endpoint is k-visible to all points of the terrain. Two points are k-visible if and only if the segment connecting them crosses at most k edges. The watchtower problem has two versions according to whether the lower endpoint of the watchtower lies exactly on a vertex (discrete watchtower problem) or not (continuous watchtower problem). We present the very first algorithm to solve the shortest k-modem watchtower problem in both discrete and continuous versions. Our algorithm runs in O(n4 log n) time for the discrete version and O(n5 log n) time for the continuous version, where n is the number of vertices of the terrain. Given a simple polygon with n vertices and a k-modem placed inside this polygon, we also improve the time complexity of computing all regions that are k-visible to the k-modem to O(n log

Guarding a Terrain by a Single k-modem Watchtower Keywords:

Guarding a Terrain by a Single k-modem Watchtower authors

bahram kouhestani

Laboratory of Algorithms and Computational Geometry, Department of Mathematics and Computer Science, Amirkabir University of Technology

farnaz sheikhi

Laboratory of Algorithms and Computational Geometry, Department of Mathematics and Computer Science, Amirkabir University of Technology

mahsa soheil shamaee

Laboratory of Algorithms and Computational Geometry, Department of Mathematics and Computer Science, Amirkabir University of Technology,

ali mohades

Laboratory of Algorithms and Computational Geometry, Department of Mathematics and Computer Science, Amirkabir University of Technology,