Watchtower arrangement method

Abstract

The present disclosure proposes a watchtower arrangement method of monitoring terrains, the watchtower arrangement method being capable of ensuring economical and efficient monitoring by optimizing a maximum height of a set watchtower while setting a limited number of watchtowers configured to monitor a plurality of points. A watchtower arrangement method according to the present disclosure includes an initial value setting step, a single watchtower arrangement determining step, and a continuous watchtower arrangement determining step.

What is claimed is: 
     
         1 . A watchtower arrangement method comprising:
 an initial value setting step of setting information on a given target terrain, in which a watchtower is to be installed, and information on apices, location apices, and the watchtower;   a single watchtower arrangement determining step of dividing a visibility region of each of the location apices into partial regions, calculating a common region of the partial region and a visibility region intersection, calculating a minimum vertical distance between a terrain boundary and the common region, and determining an arrangement of one watchtower capable of monitoring the corresponding location apex; and   a continuous watchtower arrangement determining step of determining the arrangement of the watchtower to minimize a maximum height among the watchtowers configured to monitor the continuous location apices when k watchtowers (where k is a natural number) for monitoring the given terrain are given.   
     
     
         2 . The watchtower arrangement method of  claim 1 , wherein the information on the target terrain includes an x-monotone polygonal chain on a plane corresponding to the given terrain, the information on the apex includes the number and positions of peaks on the x-monotone polygonal chain, the information on the location apex includes the number and positions of points between the apices on the x-monotone polygonal chain, and the information on the watchtower includes the number of watchtowers in the target terrain. 
     
     
         3 . The watchtower arrangement method of  claim 1 , wherein the single watchtower arrangement determining step comprises:
 dividing the visibility region into the partial regions;   calculating the common region of the partial region and the visibility region intersection; and   calculating the minimum vertical distance between the terrain boundary and the common region,   wherein the partial region is a region between a vertical line on any location apex positioned between a start point and an end point of the target location apex in the given terrain and a vertical line of another location apex adjacent to any location apex, and   wherein the visibility region intersection is an intersection of the visibility regions at the start point and the end point of the target location apex in the given terrain.   
     
     
         4 . The watchtower arrangement method of  claim 3 , wherein in the calculating of the common region of the partial region and the visibility region intersection, a common visible region, which is defined on the basis of whether the other point is capable of being viewed from one point of two arbitrary points included in the given terrain, is used, and
 wherein the common visible region is an intersection region of an upper region of any straight line, which connects the two points, and a right or left region of a region capable of being viewed from one point of the two points.   
     
     
         5 . The watchtower arrangement method of  claim 4 , wherein the two arbitrary points are two locations on the location apex. 
     
     
         6 . The watchtower arrangement method of  claim 1 , wherein the continuous watchtower arrangement determining step comprises:
 dividing a plurality of location apices included in the given terrain into two subsequences; and   determining arrangements of a plurality of watchtowers by calculating a minimum height of the watchtowers in the two subsequences with respect to k/2 watchtowers.   
     
     
         7 . The watchtower arrangement method of  claim 6 , wherein in the determining of the arrangements of the plurality of watchtowers, a binary search to the two subsequences is applied.