WATCHTOWER ARRANGEMENT METHOD

Description

CROSS-REFERENCE TO RELATED APPLICATION

The present application claims priority of Korean Patent Application No. 10-2024-0118811 filed on Sep. 2, 2024, the entire contents of which are incorporated herein for all purposes by this reference.

BACKGROUND OF THE DISCLOSURE

Field of the Disclosure

The present disclosure relates to a watchtower arrangement method, and more particularly, to 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 preset watchtower while setting a limited number of watchtowers configured to monitor a plurality of points.

Description of the Related Art

A technology for arranging a minimum number of monitors or watchtowers at appropriate points for various types of given environments is known as an art gallery problem, and this technology is utilized in various fields related to industries such as facility layout and robotics.

The art gallery problem is known as an NP-hard problem. A problem of finding a minimum number of monitors on a terrain boundary with a three-dimensional polyhedral shape has been proven to be an NP-complete problem, and the same problem in a two-dimensional space has also been proven to be the NP-complete problem. That is, it is very difficult to determine the minimum number of monitors required at a terrain boundary.

However, all the currently known methods have problems in that complexity increases exponentially as the number of temporal watchtowers increases. There is no known technology related to a method of determining a minimum number of watchtowers and a method of minimizing a height of a watchtower among the determined minimum number of watchtowers.

DOCUMENT OF RELATED ART

Non-Patent Document

• • Guarding a Terrain by Two Watchtowers, Published on-line on Jan. 7, 2009: Springer Science+Business Media, L L C 2008:

SUMMARY OF THE DISCLOSURE

The present disclosure has been made in an effort to provide 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.

Technical problems to be solved by the present disclosure are not limited to the above-mentioned technical problems, and other technical problems, which are not mentioned above, may be clearly understood from the following descriptions by those skilled in the art to which the present disclosure pertains.

In order to achieve the above-mentioned technical object, 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.

The initial value setting step includes setting information on a given target terrain, in which a watchtower is to be installed, and information on apices, location apices, and the watchtower. The single watchtower arrangement determining step includes 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. The continuous watchtower arrangement determining step includes 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.

Technical problems to be solved by the present disclosure are not limited to the above-mentioned technical problems, and other technical problems, which are not mentioned above, may be clearly understood from the following descriptions by those skilled in the art to which the present disclosure pertains.

The watchtower arrangement method according to the present disclosure described above may select the optimal point, at which the watchtower capable of monitoring a mountainous area including mountains with a plurality of apices, is to be disposed, and set the optimal height of the watchtower, thereby minimizing costs required to install the watchtower.

The effects capable of being obtained by the present disclosure are not limited to the aforementioned effects, and other effects, which are not mentioned above, will be clearly understood by those skilled in the art from the following description.

BRIEF DESCRIPTION OF THE DRAWINGS

FIGS. 1A to 1F are views illustrating a given terrain, visibility regions related to two points included in the given terrain, and an intersection region of the visibility regions.

FIGS. 2A to 2D are views illustrating a common visible region defined on the basis of whether one point of the two target points in the given terrain may be viewed from the other point.

FIG. 3 is a view illustrating an embodiment of a program for obtaining the common visible region in the given terrain.

FIG. 4 is a view illustrating an embodiment of a watchtower arrangement method according to the present disclosure.

FIG. 5 is a view illustrating an embodiment of a program for calculating (r) at a plurality of points.

FIG. 6 is a view illustrating an embodiment of a program for calculating a minimum height of a single watchtower capable of monitoring all points.

FIG. 7 is a view illustrating an embodiment of a program for calculating a minimum value of maximum heights of k watchtowers that monitor m points.

DETAILED DESCRIPTION OF THE DISCLOSURE

In order to sufficiently understand the present disclosure, advantages in operation of the present disclosure, and the object to be achieved by carrying out the present disclosure, reference needs to be made to the accompanying drawings for illustrating an embodiment of the present disclosure and contents disclosed in the accompanying drawings.

Hereinafter, the present disclosure will be described in detail through description of preferred embodiments of the present disclosure with reference to the accompanying drawings. Like reference numerals indicated in the respective drawings refer to like members.

When n peak points (where n is a natural number) included in a given terrain T are referred to as apices and a point specified between the apices in the given terrain T is referred to as a location apex, the present disclosure relates to a technology capable of minimizing a maximum height of a watchtower on the basis of the number of disposed watchtowers when k watchtowers (where k is a natural number) capable of monitoring all m location apices (where m is a natural number) in the given terrain T are intended to be disposed on the location apices. The terms “points” disclosed hereinafter will be used as generic designations including a plurality of apices and a plurality of location apices in the given terrain T.

In particular, when a single watchtower is disposed, only an intersection point of a visibility region is calculated and determined without directly calculating a visibility region of an intersection point between points. When the arrangement of the plurality of watchtowers is determined, the given terrain T is divided into partial regions by a subsequence continued in accordance with the order of the sets including the points, the divided partial regions are sorted into two groups, and the maximum height of the watchtower is determined by performing a binary search using k/2 watchtowers for the sorted groups. As a result, the present disclosure proposes a technology capable of improving a calculation speed in comparison with the related art that solves the same condition.

First, the technical terms used in the present disclosure will be described.

FIGS. 1A to 1F are views illustrating a given terrain, visibility regions related to two points included in the given terrain, and an intersection region of the visibility regions.

In FIG. 1A, the given terrain T is defined by an x-monotone polygonal chain on a plane. With reference to FIG. 1A, it can be seen that in the given terrain T, a plurality of peak points are apices, and the points specified between the apices are the location apices.

In FIG. 1B, S(i, j), which is a region between two points p_i and p_j included in the given terrain T, is defined. With reference to FIG. 1B, S(i, j), which is the region between the two points p_i and p_j, refers to a region between the two points p_i and p_j shaded between two vertical lines at the location apex p_i and the apex p_j. In this case, i and j are variables.

In FIG. 1C, a visibility region V(p_i) at the location apex p_i included in the given terrain T is defined. In FIG. 1C, the visibility region V(p_i) with respect to the location apex p_i is distinguished by being shaded.

In FIG. 1D, a visibility region V(p_j) at the apex p_j included in the given terrain T is defined. In FIG. 1D, the visibility region V(p_j) with respect to the apex p_j is distinguished by being shaded.

In FIG. 1E, an intersection V(i, j) of the visibility regions at the two continuous points p_i and p_j included in the given terrain T is defined. In FIG. 1E, the intersection V(i, j) of the visibility regions between the two continuous points p_i and p_j is distinguished by being shaded.

In FIG. 1E, an intersection W(i, j) of the visibility regions at the two points p_i and p_j refers to V(p_i)∩V(p_j). In the example illustrated in FIG. 1E, the intersection W(i, j) of the visibility regions between the two points p_i and p_j is identical to the intersection V(i, j) of the visibility regions at the two continuous points p_i and p_j.

FIGS. 2A to 2D are views illustrating a common visible region defined on the basis of whether one point of the two target points in the given terrain may be viewed from the other point.

With reference to FIGS. 2A to 2D, an intersection region of an upper region of a straight line L, which connects two points, and a right region of a region, which may be viewed from the other point, is the common visible region, and the common visible region is shaded.

FIGS. 2A and 2B illustrate an example in which the two points are respectively the location apex and the apex, and FIGS. 2C and 2D illustrate an example in which both the two points are the location apices.

FIG. 2A illustrates a case in which one apex p_m may be viewed from one location apex p₁.

With reference to FIG. 2A, a common region of an upper region of a line L, which connects the location apex p₁ and the apex p_m, and a right region, which is based on a vertical line of the apex p_m among the regions that may be viewed from the apex p_m, is shaded, and the shaded region is defined as a common visible region R(1, m) at two different points p_l and p_m. Because the apex p_m may be viewed from the location apex p_l in FIG. 2A, the line L, which is used to define the common visible region R(1, m) and connects the location apex p_l and the apex p_m, is indicated by. p₁p_m.

FIG. 2B illustrates a case in which the apex p_m cannot be viewed from the location apex p_l.

With reference to FIG. 2B, the apex p_m cannot be viewed from the location apex p_l, and thus the region, which may be viewed from the location apex p_l, is determined by an apex u positioned between the location apex p_l and the apex p_m in the given terrain T, such that the line L, which is used to define the common visible region R(1, m), is indicated by p₁u.

FIG. 2C illustrates a case in which the other location apex p_m may be viewed from one location apex p_l.

With reference to FIG. 2C, because the other location apex p_m may be viewed from one location apex p_l, the line L, which connects one location apex p_l and the other location apex p_m in FIGS. 2A and 2C, is indicated by p₁p_m.

FIG. 2D illustrates a case in which the other location apex p_m cannot be viewed from one location apex p_l.

With reference to FIG. 2D, because the other location apex p_m cannot be viewed from one location apex p_l, the line L, which is used to define the common visible region R(1, m) in FIGS. 2B and 2D, are indicated by p₁u.

In FIGS. 2B and 2D, v refers to a point at which an extension line, which connects one location apex p_i and the apex u positioned between one location apex p_i and one point p_j, meets the given terrain T when one point p_j cannot be viewed from one location apex p_i. A trunk line ē refers to a right limit line in a region that may be viewed from one point p_j in the right region based on the vertical line at one point p_j.

FIGS. 2A to 2D illustrate the common visible region R(1, m) with respect to the corresponding point p_m at the point p_l that is a reference point. If the reference point is changed to the corresponding point, a common visible region R(m, 1) may be applied by describing R(1, m) in a reverse way.

FIG. 3 is a view illustrating an embodiment of a program for obtaining the common visible region in the given terrain.

The program illustrated in FIG. 3 may obtain a common visible region R(p_i, p_j) at two arbitrary points p_i and p_j included in the given terrain T.

It can be seen that the program illustrated in FIG. 3 calculates the common visible region at the two points p_i and p_j in the given terrain T on the basis of whether the other point p_j may be viewed from one point p_i (program line 1) and whether the other point p_j is the apex (program line 7).

It is possible to obtain the common visible region at the two different points p_i and p_j among the plurality of continuous points in the given terrain T by sequentially executing the program illustrated in FIG. 3. In the program in FIG. 3, the variables given to the two points p_i and p_j are set to i and j for generalization. Because the meaning of the program illustrated in FIG. 3 may be easily understood by those skilled in the art, the meaning of the program is not described in detail.

However, it is apparent that the program proposed in FIG. 3 is characterized by being performed by distinguishing whether the other point may be viewed from one point and whether the other point belongs to the apex in the given terrain T.

FIG. 4 is a view illustrating an embodiment of a watchtower arrangement method according to the present disclosure.

With reference to FIG. 4, a watchtower arrangement method 400 according to the present disclosure includes an initial value setting step 410, a single watchtower arrangement determining step 420, and a continuous watchtower arrangement determining step 430.

In the initial value setting step 410, information on the terrain, information on the apex/location apex, and information on the watchtower to be installed. In this case, the terrain information includes an x-monotone polygonal chain on a plane. The information on the apex includes the number and positions of the apices included in the terrain information, and the information on the location apex includes the number and positions of the location apices to be monitored by the watchtowers.

The single watchtower arrangement determining step 420 includes step 421 of dividing the visibility region into partial regions, step 422 of calculating a common region of the partial region and the visibility region intersection, and step 423 of calculating a minimum vertical distance between the terrain boundary and the common region.

The continuous watchtower arrangement determining step 430 includes step 431 of dividing the point into two subsequences, and step 432 of calculating a minimum watchtower height in each of the subsequences for the k/2 watchtowers.

First, step 421 of dividing the visibility region into the partial regions, step 422 of calculating the common region of the partial region and the visibility region intersection, and step 423 of calculating the minimum vertical distance between the terrain boundary and the common region will be described.

In step 421 of dividing the visibility region into the partial regions, the plurality of partial regions is defined by using an imaginary vertical line at the plurality of apices included in the given terrain T in order to calculate the visibility region at any point. In this case, the plurality of partial regions includes S (r, r+1) that is a region between vertical lines at two points adjacent to each other among the plurality of points between a first point 1 and a last point m to be considered in the given terrain T. In the following description, it is assumed that S(r, r+1), which is the region between the vertical lines at two arbitrary points r and r+1 is a partial region at the two arbitrary points r and r+1. In this case, r (r=0, 1, . . . , m) is a variable.

Step 422 of calculating the common region of the partial region and the visibility region intersection includes obtaining a common region V(1,m)∩S(r,r+1) region of the partial region S(r, r+1) between the vertical lines of the two continuous arbitrary points r and r+1 positioned between the two points 1 and m and a visibility region intersection V(1, m) between the first point 1 and the last point m continued and subjected to the consideration. In the following description, the points are described as 1, m, i, and j or expressed as p_l, p_m, p_i, and p_j, and all the points denote designated points.

The visibility region intersection V(1, m) between the two continuous points 1 and m may be expressed by Equation 1.

V ⁡ ( 1 , m ) = ⋂ 1 < r ≤ m W ⁡ ( r - 1 , r ) ⋂ V ⁡ ( 1 ) ⋂ V ⁡ ( m ) [ Equation ⁢ 1 ]

Here, an intersection between a common visibility region W(r−1, r) between two points r−1 and r and a partial region S(r, r+1) between two points r and r+1 may be expressed by Equation 2.

W ⁡ ( r - 1 , r ) ⋂ S ⁡ ( r , r + 1 ) = R ⁡ ( r - 1 , r ) ⋂ ( S ⁡ ( r , r + 1 ) [ Equation ⁢ 2 ]

V(1,m)∩S(r,r+1) may be expressed by Equation 3 by using a relationship between Equations 1 and 2.

V ⁢ ( 1 , m ) ⋂ ( S ⁡ ( r , r + 1 ) = X 1 ⁢ ( r ) ⋂ X 2 ( r ) ⋂ X 3 ( r ) [ Equation ⁢ 3 ] X 1 ( r ) = ⋂ 1 < l ≤ r ( R ⁡ ( l - 1 , l ) ⋂ S ⁡ ( r , r + 1 ) X 2 ( r ) = ⋂ r < l ≤ m R ⁡ ( l , l - 1 ) ⋂ S ⁡ ( r , r + 1 ) X 3 ( r ) = V ⁡ ( r ) ⋂ V ⁡ ( r + 1 ) ⋂ V ⁡ ( 1 ) ⋂ V ⁡ ( m )

In order to efficiently calculate Equation 3, the fact that the intersection W(1, m) of the visibility regions at the two points 1 and m is identical to V1∩V(m) is taken into account, and the intersection W(1, m) of the visibility regions at the two points 1 and m takes into account all the location apices between two points p1 and pm at the boundary of the given terrain T of the x-monotone polygon. Therefore, Equation 3 may be calculated in linear proportion to the complexity of the terrain boundary defined as a sum of n apices and m location apices of the given terrain T.

For the same reason, the common visible region R(l−1,l) between two points p_l-1 and p_l, which takes into account other points between two points p_l-1 and p_l on the boundary of the given terrain T during the calculation process, is also linearly proportional to the complexity of T(l−1,l) that is a part of the terrain boundary.

That is, R(l−1,l) with respect to W(1,m) and all l=2, . . . , m may be calculated within the time of O(m+n). The meaning of O(m+n) will be described below.

X₁(r), X₂(r), and X₃(r) in Equation 3 may be calculated as follows.

First,

X 1 ( r ) = ⋂ 1 < l ≤ r R ⁡ ( l - 1 , l ) ⋂ S ⁡ ( r , r + 1 )

is calculated with respect to r=2, . . . , m.

For convenience, (1)=S(1,m+1) is indicated when r is one, and

ℝ ⁡ ( r ) = ∩ 1 < l ≤ r ⁢ R ⁡ ( l - 1 , l ) ⋂ S ⁡ ( r , m + 1 )

is indicated when r=2, . . . , m.

(r) is calculated with respect to r=2, . . . , m by using the fact (r)=(r−1)∩(R(r−1,r).

When r is 2, (2) is calculated by using a relationship (1)∩R(1,2)=S(1,m+1)∩R(1,2) and calculated with r=3, . . . , m while distinguishing whether the point p_r is the apex of the given terrain T and whether the point p_r is in the trunk line ē.

First, a boundary of (r) is indicated by (r), and a method of obtaining (r) from (r−1).

′(r−1) is obtained by removing all the trunk lines of (r−1) positioned at the left side of the vertical line passing through the point p_r when the point p_r is the apex in the given terrain T. It is assumed that uv is the trunk line that satisfies x(u)<x(p_r)≤x(v) among the trunk lines of V(r−1) that is obtained by is the visibility region at the point r−1. (r) is obtained by obtaining an intersection point v′ of the straight line L made by extending E′(r−1) and uv, removing all the trunk lines of ′(r−1) positioned rightward of v′, and then adding the part of the straight line L positioned rightward of v′ to ′(r−1). In case that the point pr is in the trunk line ē that is similar to the previous case, ′(r−1) is additionally updated by finding an intersection point of ′(r−1) and the straight line made by extending the trunk line ē.

FIG. 5 is a view illustrating an embodiment of a program for calculating (r) at a plurality of points.

The program illustrated in FIG. 5 obtains (r) the sequence (hereinafter, referred to as a ‘point sequence’) P=<p₁, . . . , p_m> with respect to the plurality of points between the two points 1 and m aligned in the given terrain T and at the boundary of the given terrain T.

With reference to FIG. 5, (2) may be obtained by calculating S(1,m+1)∩R(1,2) in program lines 3 and 4 and calculated within the time of O(1) because the intersection has at most five closed semi-planes.

r=3, . . . , m Calculation is performed in program lines 5 to 23 for obtaining (r) from (r−1) by using a relationship of (r) that is a boundary of (r) and the line L used to define the common visible region R(1, m). In this case, the calculation is performed in program lines 15 and 16 when the point p_r is the apex in the given terrain T. The calculation is additionally performed in lines 17 to 21 in case that the point p_r is positioned in the trunk line.

When in r=3, . . . , m, (r) means that a total of m+n trunk lines are inserted or removed at the boundary in all cases. Therefore, with respect to all r=2, . . . , m, (r) may be obtained within the time of O(m+n) By using this, X₁(r)=(r)∩S(r−1,r) with respect to all r=2, . . . , m is calculated within the time of O(m+n).

As a similar method, X₂(r) with respect to all r=m−1, . . . , l may be calculated within the time of O(m+n) by calculating the equation

ℝ ′ ( r ) = ⋂ r < l ≤ m R ⁡ ( l , l - 1 ) ⋂ S ⁡ ( 0 , r + 1 )

with respect to all r=m−1, . . . l.

X₃(r) may be calculated by obtaining V(r)∩V(r+1)∩S(r,r+1) and V(1)∩V(m).

V(r)∩V(r+1)∩S(r,r+1) with respect to all r=1, . . . , m may be calculated within the time of O(m+n) by using the feature that W(1,m) is calculated within the time of O(m+n) Because V(1) and V(m) may be calculated within the time of O(n), V(1)∩V(m) may also be calculated within the time of O(n). Therefore, V(1,m)∩S(r,r+1) with respect to r=0, . . . , m may be calculated within the time of O(m+n).

Step 423 of calculating the minimum vertical distance between the terrain boundary and the common region includes performing linear scan within the time of O(m+m) by calculating the minimum vertical distance of the common region V(1,m)∩S(r,r+1) and the terrain boundary in order to obtain a minimum height of the single watchtower capable of monitoring all the point apex.

FIG. 6 is a view illustrating an embodiment of a program for calculating a minimum height of a single watchtower capable of monitoring all points.

The program illustrated in FIG. 6 obtains a minimum height F(1, m) of the single watchtower capable of monitoring all the points by using the sequence P=<p1, . . . , pm> with respect to the given terrain T and the points between the two points 1 and m aligned at the boundary of the given terrain T.

With reference to FIG. 6, the time required to obtain an optimal height for monitoring all the points by using the single watchtower is O(m+n).

Step 430 of determining the arrangement of the continuous watchtower is a step of determining the arrangement of the watchtower capable of minimizing the maximum height of the watchtower that monitors the continuous points when k watchtowers are given, and step 430 includes step 431 of dividing the plurality of targeted points into two subsequences, and step 432 of calculating the minimum watchtower height in each of the subsequence with respect to the k/2 watchtowers. The step of determining the arrangement of the continuous watchtower is performed recursively as follows.

Step 431 of dividing the plurality of points into the two subsequences includes dividing the set of the continuous points into the two adjacent subsequences. Step 432 of calculating the minimum watchtower height in each of the subsequences with respect to the k/2 watchtowers includes calculating the minimum watchtower height in one divided subsequence by using

⌈ k 2 ⌉

watchtowers, and calculating the minimum watchtower height in the remaining divided subsequence by using

⌈ k 2 ⌉

watchtowers. The arrangement of the continuous k watchtowers is determined by recursively repeating this process.

It is assumed that a minimum value of the maximum heights in the arrangement of the watchtowers, which monitor a second point j from the continuous first point i by using k′ watchtowers, is opt(i,j,k′). In this case, step S130 of determining the arrangement of the continuous k watchtowers may include obtaining

min i ≤ l ≤ j { max ⁢ { opt ⁡ ( 1 , l , ⌊ k 2 ⌋ ) , opt ⁡ ( l + 1 , m , ⌈ k 2 ⌉ ) } }

by means of a binary search.

FIG. 7 is a view illustrating an embodiment of a program for calculating a minimum value of maximum heights of k watchtowers that monitor m points.

The program illustrated in FIG. 7 may obtain a minimum height F(1, m, k) of the watchtower, which has a maximum height among the k watchtowers that monitor the m points, with the given terrain T and the sequence P at the point aligned on the boundary of the terrain T when the number of watchtowers is k.

The program illustrated in FIG. 7 performs calculation based on a recursive function and finds an optimal height by a binary search in each of the recursive steps. A depth of a recursive tree is ┌log k┐ and there are, O(2^l log^l m) nodes at a lth level. Therefore, a total number of recursive calls is

∑ l = 0 ⌈ log ⁢ k ⌉ O ⁡ ( 2 l ⁢ log l ⁢ m ) = O ⁡ ( 2 ⌈ log 2 ⁢ k ⌉ ⁢ log ⌈ log 2 ⁢ k ⌉ ⁢ m ) = O ⁡ ( k ⁢ log ⌈ log 2 ⁢ k ⌉ ⁢ m )

Because the obtaining of OPT(i,j,1) with respect to all 1≤i≤j≤m is identical to the single watchtower arrangement determining step 420, the time O(m+n) is required. Because OPT(i,j,1) is calculated for each number of leaf nodes of OPT(1,m,k), the calculation may be performed within the time of O(k log^┌log2k┐m)×O(m+n)=O(k(m+n) log^┌log2k┐m).

The inverse Ackermann time is introduced to compare an execution time of the arrangement method according to the present disclosure and an execution time in the related art. In this case, the execution time refers to a computation time required to set the optimal watchtower.

Expression 4 refers to the inverse Ackermann time that is the amortization time per computation using the disjoint set.

O ⁡ ( α ⁡ ( n ) ) [ Expression ⁢ 4 ]

The execution time required to establish the optimal watchtower system by applying the watchtower arrangement method according to the present disclosure may be expressed by Expression 5 when the number of watchtowers is k, the number of apices in the terrain is n, the number of inner location apices is m, and the number of watchtowers is 2 (k=2).

O ⁡ ( ( m + n ) ⁢ log ⁢ m ) [ Expression ⁢ 5 ]

The execution time required to establish the watchtower system by applying the watchtower arrangement method known in the related art under the same condition may be expressed by Expression 6.

O ⁡ ( n 2 ⁢ α ⁡ ( n ) ⁢ log 3 ⁢ n ) [ Expression ⁢ 6 ]

From the comparison between Expressions 5 and 6, it may be easily understood that the execution time in Expression 5, which represents the execution time of the arrangement method according to the present disclosure, is shorter than the execution time in Expression 6 that represents the related art.

In addition, it is known in the related art that the execution time exponentially increases in accordance with an increase in number of watchtowers k under the same condition in the related art when the number of apices in the terrain is n and the number of inner location apices is m. In contrast, according to the present disclosure, the execution time slowly increases, as shown in Expression 7 when k≥3, in comparison with the related art.

O ⁡ ( k ⁡ ( m + n ) ⁢ log ⌈ log 2 ⁢ k ⌉ ⁢ m ) [ Expression ⁢ 7 ]

The watchtower arrangement method according to the present disclosure described above may determine the arrangement position of the watchtower for managing plurality of facilities in a mountainous area and optimize the maximum height of the arranged watchtower, thereby minimizing costs required to install the watchtower.

In addition, the watchtower arrangement method according to the present disclosure may be used to monitor a particular non-flat region, for example, monitor crop and environments or design security systems.

While the technical spirit of the present disclosure has been described above with reference to the accompanying drawings, the technical spirit is illustrative of the exemplary embodiments of the present disclosure and is not intended to limit the present disclosure. In addition, it is apparent that those skilled in the art to which the present disclosure pertains may variously modify and imitate the present disclosure without departing from the scope of the technical spirit of the present disclosure.