Lund University Publications

LUND UNIVERSITY LIBRARIES

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 hole-free polygon and on the time-complexity for this and related problems.

Then, we consider a generalization of the well-known 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 hole-free polygon and on the time-complexity for this and related problems.

Then, we consider a generalization of the well-known 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 t-spanner 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 higher-order Delaunay triangulations. We give an algorithm to compute which edges can be included in a higher-order Delaunay triangulation. We show that for 1-order 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)
author
supervisor
opponent
• Professor de Berg, Mark, Utrecht University
organization
publishing date
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
2000-11-24 10:15
ISSN
1650-1268
ISBN
91-7874-098-3
language
English
LU publication?
yes
id
2d042b37-1c62-44a8-8f74-a1accd636ee0 (old id 19742)
2007-05-25 12:06:17
date last changed
2019-05-21 13:03:28
```@phdthesis{2d042b37-1c62-44a8-8f74-a1accd636ee0,
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 hole-free polygon and on the time-complexity for this and related problems.<br/><br>
<br/><br>
Then, we consider a generalization of the well-known 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 t-spanner 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 higher-order Delaunay triangulations. We give an algorithm to compute which edges can be included in a higher-order Delaunay triangulation. We show that for 1-order 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         = {91-7874-098-3},
issn         = {1650-1268},
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},
}

```