Approximation Algorithms for Geometric Networks

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.

Abstract (Swedish)

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) avståndet mellan noderna. Ett sådant nätverk kan användas för att representera en mängd geometriska strukturer, såsom exempelvis en mängd städer sammankopplade via vägar.



Först betraktar vi fallet att ett specifikt nätverk är givet, där tre separata problem studeras. I första problemet antar vi att nätverket består av öar av välkopplade nätverk, och att de olika öarna är sammankopplande via ett fåtal kanter. Nätverket förbehandlas sedan så att kortaste vägar effektivt kan beräknas. I andra problemet så är det underliggande nätverket en triangulering, det vill säga en uppdelning av planet eller av ett objekts yta i trianglar. Vi visar hur en triangulering effektivt kan förenklas i ett flertal steg genom att använda modifierade kantkontraheringar. Till sist betraktar vi ett flertal individuella rörelsebanor. Dessa kan exempelvis representera rörelsemönster hos vilda djur. För dessa beräknar vi ledarindivider.



Vi betraktar sedan fallet att en mängd noder är givna, och där målet är att faktiskt skapa ett nätverk. Två sådana problem studeras. I det första problemet betraktar vi så kallade minimalt uppspännande träd, vilket är ett nätverk av minimal längd som kopplar samman alla betraktade noder. Vi beräknar en indelning av noderna i ett flertal delmängder där, om vi betraktar ett minimalt uppspännande träd för varje delmängd, målet är att minimera det största minimalt uppspännande trädet. I det andra problemet betraktar vi så kallade t-spanners, vilket är ett nätverk som tillåter vägar mellan varje par av noder med längd högst t gånger deras Euklidiska avstånd. Vi konstruera en t-spanner med låg total vikt, snabbt och enkelt, genom att först utöka det så kallade gapteoremet.



Utöver ovanstående nätverksproblem så studerar vi också ett problem där målet är att placera en mängd rektanglar av varierande storlek så att deras omgivande rektangel har minimal area, och så att ett gitter kan placeras över rektanglarna. Gittret ska då kunna placeras så att det inte skär någon av rektanglarna, och så att varje cell i gittret innehåller högst en rektangel.



Alla studerade problem är sådana att de inte enkelt tillåter beräkning av optimala lösningar i rimlig tid. Istället betraktar vi approximeringsalgoritmer, där nära-optimala lösningar produceras relativt snabbt, i så kallad polynomisk tid.

• author: Andersson, Mattias
• supervisor: Christos Levcopoulos
• opponent: Professor, Dr. van Kreveld, Marc, Utrecht University, Utrecht, The netherlands
• organization: Computer Science
• publishing date: 2007
• type: Thesis
• publication status: published
• subject: Computer Science
• keywords: control, systems, numerical analysis, Computer science, Geometric Networks, Computational Geometry, Approximation Algorithms, Datalogi, numerisk analys, system, kontroll, Systems engineering, computer technology, Data- och systemvetenskap
• pages: 184 pages
• defense location: E-huset, Ole Römers väg 3, E:1406, Lund
• defense date: 2007-09-25 13:15:00
• ISBN: 978-91-628-7250-2
• language: English
• LU publication?: yes
• id: 1aa1c2d1-1536-41df-8320-a256c0235cbb (old id 548997)
• date added to LUP: 2016-04-01 16:04:06
• date last changed: 2018-11-21 20:38:29