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

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
Subjects: Computer science
Keywords: Convex object, Coverage, Directional sensor, Image quality, Optimal orientation
Publication Number: 27545476
ISBN: 9781392569597
Copyright © 2021 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy