Advanced

From Art Galleries to Terrain Modelling --- A Meandering Path through Computational Geometry

Hammar, Mikael LU (2001)
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... (More)
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 R-trees 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. (Less)
Please use this url to cite or link to this publication:
author
opponent
  • Mitchell, J. S. B., Professor at the Department of Applied Mathematics and Statistics, SUNYSB, New York
organization
publishing date
type
Thesis
publication status
published
subject
keywords
system, numerisk analys, Datalogi, systems, control, numerical analysis, Approximation Algorithms, Computational Geometry, Online Algorithms, Art Gallery Problem, Linear Search, Traveling Salesman Problem, R-Tree, Delaunay Triangulation, Polygon Exploration, Computer science, Shortest Watchman Routes, kontroll, Mathematics, Matematik
pages
176 pages
publisher
Department of Computer Science, Lund University
defense location
E-Building room E:1406, Ole Römers väg 3
defense date
2001-11-30 10:15
ISSN
1650-1268
ISBN
91-628-5010-5
language
English
LU publication?
yes
id
52266fcd-41ca-495c-b50d-c666c429f964 (old id 42106)
date added to LUP
2007-07-31 09:57:05
date last changed
2016-09-19 08:44:53
@phdthesis{52266fcd-41ca-495c-b50d-c666c429f964,
  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.<br/><br>
<br/><br>
In part one, we study problems related to guarding, exploring and searching geometric environments. We show inapproximability results for guarding lines and &lt;i&gt;2&lt;/i&gt;-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.<br/><br>
<br/><br>
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.<br/><br>
<br/><br>
The last part is devoted to data structures in geographic information systems. We give a pioneer algorithm for constructing R-trees 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 &lt;i&gt;k&lt;/i&gt;-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.},
  author       = {Hammar, Mikael},
  isbn         = {91-628-5010-5},
  issn         = {1650-1268},
  keyword      = {system,numerisk analys,Datalogi,systems,control,numerical analysis,Approximation Algorithms,Computational Geometry,Online Algorithms,Art Gallery Problem,Linear Search,Traveling Salesman Problem,R-Tree,Delaunay Triangulation,Polygon Exploration,Computer science,Shortest Watchman Routes,kontroll,Mathematics,Matematik},
  language     = {eng},
  pages        = {176},
  publisher    = {Department of Computer Science, Lund University},
  school       = {Lund University},
  title        = {From Art Galleries to Terrain Modelling --- A Meandering Path through Computational Geometry},
  year         = {2001},
}