Geometric Decompositions and Networks  Approximation Bounds and Algorithms
(2000) In Dissertation / Department of Computer Science, Lund University 16. Abstract
 In this thesis we focus on four problems in computational geometry: In the first four chapters we consider the problem of covering an arbitrary polygon with simpler polygons, i.e., rectangles. We present several approximation algorithms for this problem, and also some lower bounds on the number of rectangles needed in a covering of a holefree polygon and on the timecomplexity for this and related problems.
Then, we consider a generalization of the wellknown Euclidean traveling salesman problem (TSP), namely the TSP with neighborhoods problem. In the TSP with neighborhoods problem we are given a collection of polygonal regions, and we seek the shortest tour that visits each neighborhood at least once. We give... (More)  In this thesis we focus on four problems in computational geometry: In the first four chapters we consider the problem of covering an arbitrary polygon with simpler polygons, i.e., rectangles. We present several approximation algorithms for this problem, and also some lower bounds on the number of rectangles needed in a covering of a holefree polygon and on the timecomplexity for this and related problems.
Then, we consider a generalization of the wellknown Euclidean traveling salesman problem (TSP), namely the TSP with neighborhoods problem. In the TSP with neighborhoods problem we are given a collection of polygonal regions, and we seek the shortest tour that visits each neighborhood at least once. We give approximation algorithms for the problem and also show a result on the hardness of the problem.
Next we turn our attention to the problem of finding a tspanner of a complete geometric graph. The aim is to produce a sparse graph with a small number of edges and with low total weight, that is almost as "good" as a complete graph. With good we mean that for every pair of points in the graph there exists a path in the spanner graph that is at most t times longer than the distance between the two points. We present several approximation algorithms for this problem.
In the final chapter of the thesis we introduce the concept of higherorder Delaunay triangulations. We give an algorithm to compute which edges can be included in a higherorder Delaunay triangulation. We show that for 1order Delaunay triangulations, most of the criteria we study can be optimized in O(n log n) time, for example, minimizing the number of local minima, the number of local extrema, the maximum angle, area triangle, and degree of any vertex. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/19742
 author
 Gudmundsson, Joachim ^{LU}
 supervisor
 opponent

 Professor de Berg, Mark, Utrecht University
 organization
 publishing date
 2000
 type
 Thesis
 publication status
 published
 subject
 keywords
 computer technology, Systems engineering, kontroll, system, Delaunay triangulation, Computational geometry, TSP with neighborhoods, geometric spanners, covering polygons, Computer science, numerical analysis, systems, control, numerisk analys, Datalogi, algebraisk topologi, algebraic topology, Geometry, Data och systemvetenskap, Geometri
 in
 Dissertation / Department of Computer Science, Lund University
 volume
 16
 pages
 151 pages
 publisher
 Department of Computer Science, Lund University
 defense location
 E:1406
 defense date
 20001124 10:15
 ISSN
 16501268
 ISBN
 9178740983
 language
 English
 LU publication?
 yes
 id
 2d042b371c6244a88f74a1accd636ee0 (old id 19742)
 date added to LUP
 20070525 12:06:17
 date last changed
 20190521 13:03:28
@phdthesis{2d042b371c6244a88f74a1accd636ee0, abstract = {In this thesis we focus on four problems in computational geometry: In the first four chapters we consider the problem of covering an arbitrary polygon with simpler polygons, i.e., rectangles. We present several approximation algorithms for this problem, and also some lower bounds on the number of rectangles needed in a covering of a holefree polygon and on the timecomplexity for this and related problems.<br/><br> <br/><br> Then, we consider a generalization of the wellknown Euclidean traveling salesman problem (TSP), namely the TSP with neighborhoods problem. In the TSP with neighborhoods problem we are given a collection of polygonal regions, and we seek the shortest tour that visits each neighborhood at least once. We give approximation algorithms for the problem and also show a result on the hardness of the problem.<br/><br> <br/><br> Next we turn our attention to the problem of finding a tspanner of a complete geometric graph. The aim is to produce a sparse graph with a small number of edges and with low total weight, that is almost as "good" as a complete graph. With good we mean that for every pair of points in the graph there exists a path in the spanner graph that is at most t times longer than the distance between the two points. We present several approximation algorithms for this problem.<br/><br> <br/><br> In the final chapter of the thesis we introduce the concept of higherorder Delaunay triangulations. We give an algorithm to compute which edges can be included in a higherorder Delaunay triangulation. We show that for 1order Delaunay triangulations, most of the criteria we study can be optimized in O(n log n) time, for example, minimizing the number of local minima, the number of local extrema, the maximum angle, area triangle, and degree of any vertex.}, author = {Gudmundsson, Joachim}, isbn = {9178740983}, issn = {16501268}, keyword = {computer technology,Systems engineering,kontroll,system,Delaunay triangulation,Computational geometry,TSP with neighborhoods,geometric spanners,covering polygons,Computer science,numerical analysis,systems,control,numerisk analys,Datalogi,algebraisk topologi,algebraic topology,Geometry,Data och systemvetenskap,Geometri}, language = {eng}, pages = {151}, publisher = {Department of Computer Science, Lund University}, school = {Lund University}, series = {Dissertation / Department of Computer Science, Lund University}, title = {Geometric Decompositions and Networks  Approximation Bounds and Algorithms}, volume = {16}, year = {2000}, }