COMING SOON! PQDT Open is getting a new home!

ProQuest Open Access Dissertations & Theses will remain freely available as part of a new and enhanced search experience at www.proquest.com.

Questions? Please refer to this FAQ.

# Dissertation/Thesis Abstract

Optimal Algorithm to Cover a Convex Object Using Minimum Number of Directional Sensors
by Karande, Harshal Manohar, M.S., California State University, Long Beach, 2019, 50; 27545476
Abstract (Summary)

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.

Indexing (document details)
 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 Source Type: DISSERTATION Subjects: Computer science Keywords: Convex object, Coverage, Directional sensor, Image quality, Optimal orientation Publication Number: 27545476 ISBN: 9781392569597