In the coverage problem, an object of interest is covered using the minimum number of directional sensors. Covering an object using the minimum number of sensors while maintaining high-quality standards has applications in surveillance to detect intruders. We consider covering the surface of a convex object modeled as a convex polygon. To cover the convex object, we present a dynamic programming algorithm to cover a convex object using an optimal number of directional sensors. The solution takes an approach of utilizing the coverage capacity of the directional sensor to cover edges and vertices of the object. First, we present a solution that optimally orients the directional sensors to cover a straight-line object. Then we extend the solution to fully cover a convex object by maximizing the coverage of directional sensors covering the vertices. The algorithm chooses an appropriate position for the directional sensor to cover a portion depending on whether it is an edge or a vertex of the object. We propose the concept of canonical distance, which is the maximum distance covered by a path of distance k. The algorithm iterates over canonical distances, k = 0, 1, 2,...n, starting at each vertex of the object to find canonical paths of distance k and records the positions of directional sensors which are then used to calculate the canonical paths of higher distances. Hence, the algorithm considers all the possible paths and give the optimal solution in O(n2) time to cover the convex object with n-edges.
|Advisor:||Morales Ponce, Oscar|
|Commitee:||Lam, Shui, Aliasgari, Mehrdad|
|School:||California State University, Long Beach|
|Department:||Computer Engineering and Computer Science|
|School Location:||United States -- California|
|Source:||MAI 81/7(E), Masters Abstracts International|
|Keywords:||Convex object, Coverage, Directional sensor, Image quality, Optimal orientation|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be