Abstract
We give approximation and online algorithms as well as data structures for some well studied problems in computational geometry. The thesis is divided into three parts.
In part one, we study problems related to guarding, exploring and searching geometric environments. We show inapproximability results for guarding lines and <i>2</i>link polygons, question stated time bounds for computing shortest watchman routes and give a competitive strategy for exploring rectilinear polygons. We also give matching upper and lower bounds for two large classes of strategies for searching concurrent rays in parallel.
The second part considers generalisations of the travelling salesman problem. We give online strategies for the time dependent travelling salesman problem and approximation algorithms and inapproximability results for versions of the kinetic travelling salesman problem. A highlight of the thesis is the exponential lower bound on the approximation ratio for the kinetic travelling salesman problem restricted to expanding point sets.
The last part is devoted to data structures in geographic information systems. We give a pioneer algorithm for constructing Rtrees optimised for point location queries. This data structure is used in databases for geometrical objects containing an exceptional amount of data. Finally, bringing the thesis to a close, we suggest a generalisation of the Delaunay triangulation that we call the <i>k</i>order Delaunay triangulation. This geometric structure corresponds to a similar generalisation of the Voronoi diagram, and is predicted to be of value in automating the removal of artifacts in terrain modelling.
In part one, we study problems related to guarding, exploring and searching geometric environments. We show inapproximability results for guarding lines and <i>2</i>link polygons, question stated time bounds for computing shortest watchman routes and give a competitive strategy for exploring rectilinear polygons. We also give matching upper and lower bounds for two large classes of strategies for searching concurrent rays in parallel.
The second part considers generalisations of the travelling salesman problem. We give online strategies for the time dependent travelling salesman problem and approximation algorithms and inapproximability results for versions of the kinetic travelling salesman problem. A highlight of the thesis is the exponential lower bound on the approximation ratio for the kinetic travelling salesman problem restricted to expanding point sets.
The last part is devoted to data structures in geographic information systems. We give a pioneer algorithm for constructing Rtrees optimised for point location queries. This data structure is used in databases for geometrical objects containing an exceptional amount of data. Finally, bringing the thesis to a close, we suggest a generalisation of the Delaunay triangulation that we call the <i>k</i>order Delaunay triangulation. This geometric structure corresponds to a similar generalisation of the Voronoi diagram, and is predicted to be of value in automating the removal of artifacts in terrain modelling.
Original language  English 

Qualification  Doctor 
Awarding Institution  
Supervisors/Advisors 

Award date  2001 Nov 30 
Publisher  
ISBN (Print)  9162850105 
Publication status  Published  2001 
Bibliographical note
Defence detailsDate: 20011130
Time: 10:15
Place: EBuilding room E:1406, Ole Römers väg 3
External reviewer(s)
Name: Mitchell, J. S. B.
Title: [unknown]
Affiliation: Professor at the Department of Applied Mathematics and Statistics, SUNYSB, New York

Subject classification (UKÄ)
 Computer Science
Keywords
 system
 numerisk analys
 Datalogi
 systems
 control
 numerical analysis
 Approximation Algorithms
 Computational Geometry
 Online Algorithms
 Art Gallery Problem
 Linear Search
 Traveling Salesman Problem
 RTree
 Delaunay Triangulation
 Polygon Exploration
 Computer science
 Shortest Watchman Routes
 kontroll
 Mathematics
 Matematik