Search for dissertations about: "Shortest Watchman Routes"

Found 2 swedish dissertations containing the words Shortest Watchman Routes.

2. 1. From Art Galleries to Terrain Modelling --- A Meandering Path through Computational Geometry

   Author : Mikael Hammar; Data Vetenskap; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; system; numerisk analys; Datalogi; systems; control; numerical analysis; Approximation Algorithms; Computational Geometry; Online Algorithms; Art Gallery Problem; Linear Search; Traveling Salesman Problem; R-Tree; Delaunay Triangulation; Polygon Exploration; Computer science; Shortest Watchman Routes; kontroll; Mathematics; Matematik;

   Abstract : We give approximation and online algorithms as well as data structures for some well studied problems in computational geometry. The thesis is divided into three parts. In part one, we study problems related to guarding, exploring and searching geometric environments. READ MORE

4. 2. The Euclidean traveling salesman problem with neighborhoods and a connecting fence

   Author : Håkan Jonsson; Luleå tekniska universitet; []
   Keywords : NATURVETENSKAP; NATURAL SCIENCES; Dependable Communication and Computation Systems; Kommunikations- och beräkningssystem;

   Abstract : An important class of problems in robotics deals with the planning of paths. In this thesis, we study this class of problems from an algorithmic point of view by considering cases where we have complete knowledge of the environment and each solution must ensure that a point-sized robot capable of moving continuously and turning arbitrarily accomplishes the following: (1) visits a given set of objects attached to an impenetrable simple polygon in the plane, and (2) travels along a path of minimum length over all the possible paths that visit the objects without crossing the polygon. READ MORE