Departments  

Book Series (70) 
831

Humanities 
1712

Natural Sciences 
4829

Mathematics  203 
Informatics  257 
Physics  912 
Chemistry  1215 
Geosciences  114 
Human medicine  191 
Stomatology  7 
Veterinary medicine  66 
Pharmacy  130 
Biology  760 
Biochemistry, molecular biology, gene technology  94 
Biophysics  18 
Domestic and nutritional science  37 
Agricultural science  919 
Forest science  193 
Horticultural science  12 
Environmental research, ecology and landscape conservation  120 
Engineering 
1370

Common 
66

Table of Contents, Datei (61 KB)
Extract, Datei (1.8 MB)
ISBN13 (Printausgabe)  3869558296 
ISBN13 (Hard Copy)  9783869558295 
ISBN13 (eBook)  9783736938298 
Language  English 
Page Number  158 
Edition  1 Aufl. 
Volume  0 
Publication Place  Göttingen 
Place of Dissertation  TU braunschweig 
Publication Date  20110727 
General Categorization  Dissertation 
Departments 
Mathematics
Informatics 
This work deals with geometric problems and the use of limited capability agents for these problems. Exploration and guarding problems have been extensively studied in computational geometry. The basic task is to monitor an environment (a polygon) either with a mobile guard or with a number of sta¬tionary guards (or guards with hard restrictions on the allowed movements). Though all these problems are easy to formulate—and have realworld interpretations that vividly illustrate them—some of these problems (as the classical art gallery problem) are hard to solve. The task of exploring an environment becomes more challenging if the environment is not known in advance, that is, there is no given ground plan and only areas that have already been visibly encountered by the explorer are known. Problems with this kind of uncertainty are called online problems. For oﬄine problems the ground plan of the environment is known in advance. In this work we study one oﬄine exploration problem and one exploration and guarding problem in the oﬄine and online version, where the focus is on the latter. For our problems we do not deal with “almighty” explorers, but face limits on their perceptive capabilities. Other types of geometric problems can exploit this kind of limited agents: We present an exact and fast algorithm for an image analysis task with polyominoshaped objects on a grid.
Distributed Vision with Smart Pixels. An important image analysis task is the identiﬁcation of objects present in a given image. If these objects are to be processed automatically, not only the identiﬁcation of the objects themselves, but also of certain attributes is of interest. The images we treat are pixel (grid) images, with a possibly huge number of intertwined objects. We make an assumption on the pixels: Besides light detection, they can perform simple computations and communicate with their grid neighbors (smart pixels). Our goal is to extract attributes, such as the center of gravity or orientation, for each object in the image. In particular, we want to give a fast algorithm for this task. We show how the use of mobile agents, mimicked by messages sent by the pixels, allows for an exact algorithm—an agent sweep—that can cope with intertwined objects. We present how the attributes can be expressed as moments (of a random variable, considering the pixels as a point set in R2) and how the sweep accumulates the necessary information. For the algorithm we prove a runtime of only O(W + H), with W and H being the width and height of the smallest bounding box for an object, respectively.
Exploration with a Myopic Watchman with Discrete Vision. In the classical watchman route problem the task is to ﬁnd a shortest tour for an explorer such that each point of a given polygon is visible from at least one point of the tour. For this problem exact algorithms for a variety of polygon classes exist. We study this problem with two restrictions on the watchman’s capabilities: The scan range is limited and visibility information can only be acquired at discrete points, “scanpoints”. A scanpoint in combination with all points of the polygon that can be seen from the point and lie within its scan range form a scan. The scans must fully cover the given polygon. The cost for a tour of this watchman is a linear combination of tour length and number of scan points used along this tour. We show that this problem is NPhard and present approximation algorithms for diﬀerent variants: A 2.5approximation for rectilinear grid polygons and unit L∞ scan range, a 4approximation for rectilinear grid polygons and unit L2 scan range and a
πr πr π
max(21 , + + )approximation for the case of general polygons, an L2
4 a 22
scan range and a bounded ratio r/a between visibility range r and minimum side length a. All these approximation algorithms can also be applied for the bicriteria version, that is, approximating the scan number and the tour length separately.
Exploration and Triangulation with a Swarm of Robots. The art gallery problem asks for a minimum number of (stationary) guards that al¬low for visibility coverage of a given polygon. Another classical problem in computational geometry is triangulation: The partition of a given polygon into triangles. We study a guarding problem linked to both of these problems: A swarm of agents with limited communication range has to establish a triangulated network in a given polygon. The edge lengths are limited to the communication range. The task is not only to give the positions, but to move to these locations in a connected fashion. Our goal is to minimize the number of robots used for this task, or, if the number of robots is limited, to cover as much area as possible with the triangulation established by these robots. We present NPhardness results for both problems. Our focus is on the online variants, we give a lower bound of 6/5 for the competitive ratio for any strategy for the ﬁrst problem, as well as a 3competitive strategy. We prove that the second problem does not allow for a constant competitive ratio.