Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 6 of 6 for “"art gallery problem"”.
-
The art gallery problem in polyomino corridors
Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms
-
Visibility analysis of landmark-based navigation
This thesis introduces and examines the chromatic art gallery problem. The chromatic art gallery problem asks for the minimum number of landmark classes required to ensure that every point in an input polygon sees at least one landmark but sees no more than one landmark of any particular class. The …
-
A pseudo-polynomial time O(log² n)-approximation algorithm for art gallery problems
… n)-approximation algorithm for a variant of the art gallery problem the point-guard problem. The point-guard problem involves finding the minimum number of points and their positions so that guards located at these points cover the interior of the art gallery. Our algorithm is pseudo-polynomial …
-
Guarding Polygons With Mutually Visible π-Guards
We study a variant of the classic art gallery problem focusing on mutually visible π-guards. In this variation, for a given polygon P, we aim to place the minimum number of guards of 180° field of view at vertices such that they guard P, and for each guard g there is a guard g' such that g and g' …
-
An art gallery approach to ensuring that landmarks are distinguishable
How many different classes of partially distinguishable landmarks are needed to ensure that a robot can always see a landmark without simultaneously seeing two of the same class? To study this, we introduce the chromatic art gallery problem. A guard set S ⊂ P is a set of points in a polygon P such …
-
Geometric Hitting Sets and Their Variants
… thesis explores a few geometric optimization problems that arise</p><p>in robotics and sensor networks. In particular we present efficient</p><p>algorithms for the hitting-set problem and the budgeted hitting-set problem.</p><p>Given a set of objects and a collection of subsets of the …