Search
×

OR

Create a Shvoong account from scratch

×

OR

×

OR

Shvoong Home>Science>Mathematics>APPROXIMATION ALGORITHMS FOR GEOMETRIC NETWORKS Summary

# APPROXIMATION ALGORITHMS FOR GEOMETRIC NETWORKS

Book Summary   by:CosmicBliss     Original Authors:

The main contribution of this thesis is the 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 eight 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, the thesis study three separate problems. In the first it considers the case of interconnected ‘island’ of well-connected networks, in which shortest paths are computed. In the second the input network is a triangulation. It efficiently simplify this triangulation using edge contractions. Finally, Mattias considers individual movement trajectories representing, for example, wild animals where it compute leadership individuals. Next, he considers the case that only a set of vertices is given, and that the aim is to actually construct a network. Two such problems are considered.
In the first one he computes a partition of the vertices into several subsets where, considering the minimum spanning tree (MST) for each subset, he aims to minimize the largest MST. The other problem is to construct a t-spanner of low weight fast and simple which is done by first extending the so-called gap theorem. In addition to geometric network problems, the author and the Department of Computer Science also study a problem where they 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 interest any rectangle, and each cell of the grid should contain at most one rectangle. All studies are such that they do not easily allow computation of optimal solutions in feasible time. Instead approximation algorithms are considered, where near-optimal solutions are produced in polynomial time.
Published: September 27, 2007
 Please Rate this Summary : 1 2 3 4 5
Tags:
 Use our Content Translate Send Link Print Share