Approximation Algorithms for Geometric Networks
Popular Abstract in Swedish Det huvudsakliga bidraget i denna avhandling är approximationsalgoritmer för flera problem inom beräkningsgeometri. Den underliggande strukturen för de flesta problemen är ett geometriskt nätverk. Ett geometriskt nätverk är, i sin mest abstrakta form, en mängd noder parvis kopplade med en kant, sådan att vikten på denna kant är lika med det Euklidiska (geometriska) avstThe 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. S