Approximation Algorithms for Geometric Networks

DSpace Repository

Approximation Algorithms for Geometric Networks

Overview

Detailed record

dc.contributor.author Andersson, Mattias
dc.date.accessioned 2009-09-28T13:34:07Z
dc.date.available 2009-09-28T13:34:07Z
dc.date.issued 2007
dc.identifier.isbn 978-91-628-7250-2
dc.identifier.issn 1650-1268
dc.identifier.uri http://hdl.handle.net/2043/8616
dc.description.abstract The main contribution of this thesis is approximation algorithms for several computational geometry problems. The underlying structure for most of the problems studied is a geometric network. A geometric network is, in its abstract form, a set of vertices, pairwise connected with an edge, such that the weight of this connecting edge is the Euclidean distance between the pair of points connected. Such a network may be used to represent a multitude of real-life structures, such as, for example, a set of cities connected with roads. Considering the case that a specific network is given, we study three separate problems. In the first problem we consider the case of interconnected `islands' of well-connected networks, in which shortest paths are computed. In the second problem the input network is a triangulation. We efficiently simplify this triangulation using edge contractions. Finally, we consider individual movement trajectories representing, for example, wild animals where we compute leadership individuals. Next, we consider the case that only a set of vertices is given, and the aim is to actually construct a network. We consider two such problems. In the first one we compute a partition of the vertices into several subsets where, considering the minimum spanning tree (MST) for each subset, we aim to minimize the largest MST. The other problem is to construct a $t$-spanner of low weight fast and simple. We do this by first extending the so-called gap theorem. In addition to the above geometric network problems we also study a problem where we aim to place a set of different sized rectangles, such that the area of their corresponding bounding box is minimized, and such that a grid may be placed over the rectangles. The grid should not intersect any rectangle, and each cell of the grid should contain at most one rectangle. All studied problems are such that they do not easily allow computation of optimal solutions in a feasible time. Instead we consider approximation algorithms, where near-optimal solutions are produced in polynomial time. In addition to the above geometric network problems we also study a problem where we aim to place a set of different sized rectangles, such that the area of their corresponding bounding box is minimized, and such that a grid may be placed over the rectangles. The grid should not intersect any rectangle, and each cell of the grid should contain at most one rectangle. All studied problems are such that they do not easily allow computation of optimal solutions in a feasible time. Instead we consider approximation algorithms, where near-optimal solutions are produced in polynomial time. en
dc.language.iso eng en
dc.publisher Lund University en
dc.subject.classification Technology en
dc.title Approximation Algorithms for Geometric Networks en
dc.type Doctoral Thesis en
dc.identifier.paperprint 0 en
dc.contributor.department Malmö University. School of Technology en
dc.subject.srsc Research Subject Categories::TECHNOLOGY::Information technology en
dcterms.type Doctoral Thesis, monograph
 Find Full text Files for download

There are no files associated with this item.

This item appears in the following Collection(s)

Overview

Search


Browse

My Account

Statistics