Fixed-Parameter Algorithms for Optimal Convex Partitions and Other Results
(2006)- Abstract
- In this thesis I study two-dimensional geometric optimization problems for which it is difficult to find efficient, exact, deterministic algorithms. All known solutions to these problems require time that is exponential in the total size of the input. The work done in this thesis is a contribution to the research directed at attacking and coping with such NP hard problems in computational geometry.
A promising way to attack and cope with such problems is to find an algorithm that is exponential in the size of only one input parameter and polynomial in the size of all other input parameters. Such an algorithm is called a fixed parameter algorithm, because if we fix the single troublesome input at any one value, the... (More) - In this thesis I study two-dimensional geometric optimization problems for which it is difficult to find efficient, exact, deterministic algorithms. All known solutions to these problems require time that is exponential in the total size of the input. The work done in this thesis is a contribution to the research directed at attacking and coping with such NP hard problems in computational geometry.
A promising way to attack and cope with such problems is to find an algorithm that is exponential in the size of only one input parameter and polynomial in the size of all other input parameters. Such an algorithm is called a fixed parameter algorithm, because if we fix the single troublesome input at any one value, the problem can be solved efficiently (i.e.in polynomial time). In this thesis, I give algorithms based on this idea. Generally, the input I work with has n vertices and I choose the number k of vertices lying in the interior of the boundary of the input as the fixed parameter.
Based on this idea the results in this thesis include algorithms for the minimum weight triangulation problem, the minimum weight convex partition problem, and the minimum number convex partition problem:
I present four fixed parameter algorithms for finding the minimum weight triangulation of a simple polygon with n-k vertices on the perimeter and k vertices in the interior (hole vertices), that is, or a total of n vertices. All four algorithms have been implemented in Java and I report results of experiments carried out with these implementations. For the minimum weight and minimum number convex partition problem I present fixed parameter algorithms for a convex polygon with n k vertices on the perimeter and k vertices in the interior (hole vertices). However, the results for these two problems also hold for the more general case where the input is an n-vertex planar straight line graph and k is the total number of holes and/or reflex vertices inside the convex hull. For the special case of the minimum weight convex partition problem of a convex polygon with a single hole vertex (the so-called local minimum weight convex partition problem), I present an optimal algorithm and an approximation algorithm.
In addition to the above closely connected results, this thesis presents results on the following related subjects: I show bounds on optimally triangulating connected subsets of the minimum weight convex partition of simple polygons and points in the plane. I consider the minimum line covering problem, which is also known to be NP-hard.
I give exact and approximate algorithms and a lower time bound for restricted variants of this problem. Finally, I discuss minimum spanning trees with bi chromatic vertices. I present tight upper bounds on the maximum degree of a node in the color conforming minimum weight spanning tree and discuss bounds on the total length of the edges. (Less) - Abstract (Swedish)
- Popular Abstract in Swedish
I denna avhandling studerar jag tvådimensionella geometriska optimeringsproblem. Gemensamt för många praktiskt och teoretiskt intressanta problemställningar inom området är att det är mycket svårt att ta fram optimala lösningar. Det tar helt enkelt alltför lång tid att undersöka alla möjligheter för probleminstanser med stora mängder indata då beräkningstiden växer exponentiellt med storleken på indata. Avhandlingen behandlar sådana NP-svåra problem inom området computational geometry.
För en del algoritmer som hanterar problemen växer beräkningstiden exponentiellt endast i en indataparameter, när det gäller övriga parametrar växer den polynomiellt. Dessa algoritmer kallas... (More) - Popular Abstract in Swedish
I denna avhandling studerar jag tvådimensionella geometriska optimeringsproblem. Gemensamt för många praktiskt och teoretiskt intressanta problemställningar inom området är att det är mycket svårt att ta fram optimala lösningar. Det tar helt enkelt alltför lång tid att undersöka alla möjligheter för probleminstanser med stora mängder indata då beräkningstiden växer exponentiellt med storleken på indata. Avhandlingen behandlar sådana NP-svåra problem inom området computational geometry.
För en del algoritmer som hanterar problemen växer beräkningstiden exponentiellt endast i en indataparameter, när det gäller övriga parametrar växer den polynomiellt. Dessa algoritmer kallas fixed parameter algorithms, eftersom de kan lösa problemet effektivt om man bestämmer ett värde för den svåra parametern. Avhandlingen presenterar algoritmer av den här typen. Generellt beskriver vi det så att med n noder som indata väljer man att utgå från att k stycken av dessa ligger innanför gränserna för partitioneringen. Givet att man har fixerat k kan man lösa problemet effektivt.
Med denna idé som utgångspunkt har jag tagit fram algoritmer för en rad intressanta problem, bl.a. the minimum weight triangulation problem (fyra olika algoritmer för problemet har implementerats i Java och utvärderats.), the minimum weight convex partition problem och the minimum number convex partition problem. Att dela upp en polygon i konvexa delar (convex partitions) innebär att man delar upp hela polygonens inre i icke-överlappande konvexa element. Dessa delar kan ha en gemensam form (t.ex. trianglar, kvadrater, rektanglar, trapetsoider) eller så tillåter man godtyckliga konvexa polygoner. Tekniken är ett viktigt första steg i många geometriska algoritmer då de flesta geometriska problem kan lösas både snabbare och enklare för konvexa objekt än icke-konvexa. Alltså har vi en bättre utgångspunkt när vi kan dela upp ett icke-konvext objekt i ett litet antal konvexa element eftersom det förenklar det fortsatta arbetet.
Vanligtvis vill man minimera uppdelningen i konvexa delar på något sätt. Till exempel kan man vilja minimera antalet delar (minimum number convex partition). I andra sammanhang vill man minimera den totala längden på delarnas sidor (minimum weight convex partitioning) Vidare vill man ibland ha en speciell form på delarna, t.ex. trianglar. Trianglar har bara tre sidor, därför är alla geometriska operationer som enklast att utföra på just trianglar. Samtidigt ? eftersom trianglar har tre sidor ? är inte triangulering rätt metod om man vill ha ett litet antal konvexa delar, därför studeras triangulering framförallt med målet att minimera den totala längden på trianglarnas sidor (minimum weight triangulation).
Exempel på tillämpningsområden är datorgrafik, bildbehandling, databassystem och datakompression.
Utöver algoritmer för dessa problem presenterar avhandlingen ytterligare resultat. Jag fastställer gränser för hur snabbt en algoritm kan arbeta som ger en optimal lösning på ett trianguleringsproblem. För en variant av the minimum line covering problem (att täcka indatapunkter med minimalt antal räta linjer) ger jag såväl exakta som approximativa algoritmer samt undre tidsgränser. Vidare behandlar jag minimum spanning trees with bi-chromatic vertices, som avser hur man kan generera geometriska kopplingar av minimal längd med vissa restriktioner. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/546843
- author
- Grantson Borgelt, Magdalene LU
- supervisor
- opponent
-
- Prof. Dr. Klein, Rolf, University of Bonn, Bonn, Germany
- organization
- publishing date
- 2006
- type
- Thesis
- publication status
- published
- subject
- keywords
- control, Datalogi, numerical analysis, Convex Partition, Computer science, Triangulation, kontroll, system, numerisk analys, systems, Fixed-Parameter Algorithm, Spanning Tree
- pages
- 169 pages
- publisher
- Department of Computer Science, Lund University
- defense location
- Room E:1406, Ole Römers väg 3 (building E, LTH), Lund University.
- defense date
- 2006-06-14 10:15:00
- ISBN
- 91-628-6801-2
- language
- English
- LU publication?
- yes
- id
- 7ce0a3a5-8421-472d-b6b0-d89acb4fd9af (old id 546843)
- date added to LUP
- 2016-04-01 16:54:56
- date last changed
- 2018-11-21 20:45:12
@phdthesis{7ce0a3a5-8421-472d-b6b0-d89acb4fd9af,
abstract = {{In this thesis I study two-dimensional geometric optimization problems for which it is difficult to find efficient, exact, deterministic algorithms. All known solutions to these problems require time that is exponential in the total size of the input. The work done in this thesis is a contribution to the research directed at attacking and coping with such NP hard problems in computational geometry.<br/><br>
<br/><br>
A promising way to attack and cope with such problems is to find an algorithm that is exponential in the size of only one input parameter and polynomial in the size of all other input parameters. Such an algorithm is called a fixed parameter algorithm, because if we fix the single troublesome input at any one value, the problem can be solved efficiently (i.e.in polynomial time). In this thesis, I give algorithms based on this idea. Generally, the input I work with has n vertices and I choose the number k of vertices lying in the interior of the boundary of the input as the fixed parameter.<br/><br>
<br/><br>
Based on this idea the results in this thesis include algorithms for the minimum weight triangulation problem, the minimum weight convex partition problem, and the minimum number convex partition problem:<br/><br>
<br/><br>
I present four fixed parameter algorithms for finding the minimum weight triangulation of a simple polygon with n-k vertices on the perimeter and k vertices in the interior (hole vertices), that is, or a total of n vertices. All four algorithms have been implemented in Java and I report results of experiments carried out with these implementations. For the minimum weight and minimum number convex partition problem I present fixed parameter algorithms for a convex polygon with n k vertices on the perimeter and k vertices in the interior (hole vertices). However, the results for these two problems also hold for the more general case where the input is an n-vertex planar straight line graph and k is the total number of holes and/or reflex vertices inside the convex hull. For the special case of the minimum weight convex partition problem of a convex polygon with a single hole vertex (the so-called local minimum weight convex partition problem), I present an optimal algorithm and an approximation algorithm.<br/><br>
<br/><br>
In addition to the above closely connected results, this thesis presents results on the following related subjects: I show bounds on optimally triangulating connected subsets of the minimum weight convex partition of simple polygons and points in the plane. I consider the minimum line covering problem, which is also known to be NP-hard.<br/><br>
<br/><br>
I give exact and approximate algorithms and a lower time bound for restricted variants of this problem. Finally, I discuss minimum spanning trees with bi chromatic vertices. I present tight upper bounds on the maximum degree of a node in the color conforming minimum weight spanning tree and discuss bounds on the total length of the edges.}},
author = {{Grantson Borgelt, Magdalene}},
isbn = {{91-628-6801-2}},
keywords = {{control; Datalogi; numerical analysis; Convex Partition; Computer science; Triangulation; kontroll; system; numerisk analys; systems; Fixed-Parameter Algorithm; Spanning Tree}},
language = {{eng}},
publisher = {{Department of Computer Science, Lund University}},
school = {{Lund University}},
title = {{Fixed-Parameter Algorithms for Optimal Convex Partitions and Other Results}},
year = {{2006}},
}