Indexed by:
Abstract:
With the development of the smart city, camera sensors have attracted more and more research interests from both academic researchers and industrial engineers. Given a set of points of interests (POI) and a set of cameras, practical applications require to deploy these cameras with the minimum cost so that these POIs can be fully covered by these cameras. In this paper, we study a problem called Min-Num LTC-CS, which is, given a set of POIs located on a line segment and a set of cameras distributed on the plane, to choose a minimum number of cameras so that these POIs can be fully covered by the sensing ranges of these cameras. We first propose a grouping algorithm by grouping the POIs according to whether they can be covered by the same camera with certain rotation angle and then construct a graph using these POI groups. We show that there exists a feasible constrained st-flow if and only if there exists a subset of cameras that can completely cover these POIs. Then we propose an LP formulation for the constrained flow problem and prove that any basic solution of the LP formulation is integral, which consequently leads to an optimal solution to Min-Num LTC-CS by solving this LP formulation. Lastly, extensive numerical experiments are conducted to demonstrate the practical performance of our algorithms. © 2021, Springer Nature Switzerland AG.
Keyword:
Reprint 's Address:
Email:
Source :
ISSN: 0302-9743
Year: 2021
Volume: 13135 LNCS
Page: 12-24
Language: English
0 . 4 0 2
JCR@2005
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: