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)
Please use this url to cite or link to this publication:
https://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
- 2000-11-24 10:15:00
- ISSN
- 1650-1268
- ISBN
- 91-7874-098-3
- language
- English
- LU publication?
- yes
- id
- 2d042b37-1c62-44a8-8f74-a1accd636ee0 (old id 19742)
- date added to LUP
- 2016-04-01 16:00:19
- date last changed
- 2021-05-05 16:33:15
@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}},
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}},
language = {{eng}},
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}},
url = {{https://lup.lub.lu.se/search/files/4540703/1001965.pdf}},
volume = {{16}},
year = {{2000}},
}