Fachbereiche  

Buchreihen (78) 
1030

Geisteswissenschaften 
1940

Naturwissenschaften 
5048

Mathematik  210 
Informatik  280 
Physik  941 
Chemie  1275 
Geowissenschaften  122 
Humanmedizin  217 
Zahn, Mund und Kieferheilkunde  9 
Veterinärmedizin  78 
Pharmazie  139 
Biologie  783 
Biochemie, Molekularbiologie, Gentechnologie  107 
Biophysik  21 
Ernährungs und Haushaltswissenschaften  40 
Land und Agrarwissenschaften  954 
Forstwissenschaften  197 
Gartenbauwissenschaft  14 
Umweltforschung, Ökologie und Landespflege  128 
Ingenieurwissenschaften 
1518

Allgemein 
77

Leitlinien Unfallchirurgie
5. Auflage bestellen 
Inhaltsverzeichnis, Datei (61 KB)
Leseprobe, Datei (1,8 MB)
ISBN13 (Printausgabe)  3869558296 
ISBN13 (Printausgabe)  9783869558295 
ISBN13 (EBook)  9783736938298 
Sprache  Englisch 
Seitenanzahl  158 
Auflage  1 Aufl. 
Band  0 
Erscheinungsort  Göttingen 
Promotionsort  TU braunschweig 
Erscheinungsdatum  27.07.2011 
Allgemeine Einordnung  Dissertation 
Fachbereiche 
Mathematik
Informatik 
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.