Course 2D5345: Introductory Computational Geometry for Geoinformatics Applications

Schedule Fall 1997:

7 Mondays 13.15-15, beginning week 44 (Oct. 27)
First lecture in Room 4523 Plan 5, Lindstedtsv. 5. Following weeks: Room 1537 Plan 5, Lindstedtsv. 3

Goal:

Present and analyse a selection of geometric concepts, data structures and algorithms which have found important applications in geoinformatics.

Throughout the course, emphasis is placed on methods which can be implemented in a robust, efficient, and reasonably transparent manner.

Also, whenever possible, the presentation emphasises general algorithmic principles, such as plane-sweep, divide-and-conquer, and basic network search algorithms.

Contents:

The course is divided into three parts.

The presentation starts by informally introducing basic topological and geometrical concepts. Methods for representing plane geometric objects in computers are then described. A set of fundamental computational geometry problems in the plane are introduced and discussed, such as convexity, shortest paths, and neighbourhood.

The second part of the course deals with two important applications: plane network problems and TIN (Triangulated Irregular Network) models and their associated basic computational issues.

The third and last part of the course discusses a special but very important topic in GIS: the design of data structures and access algorithms for efficient storage and retrieval of spatial data in databases. Basic file organisation techniques are covered. Indexing techniques for point, line, and region data are surveyed.

The course consists of lectures and mandatory computer exercises.

Examination:

Examination is taken in the form of group projects in program system development and evaluation, together with written and oral presentations. Presentations of special topics in the course will also give you credit.

Prerequisites:

Since the course is intended to be relevant for all CGI Ph D students, only basic programming competence will be required to be able to follow the course.

However, to carry out the group projects, usually considerable computer science maturity will be required from the group as a whole, as well as domain knowledge and management and documentation skills.

Therefore, we will form "cross-disciplinary" project groups, where the different competences of group members is employed in different project roles.

Course overview:

Introduction to concepts of two-dimensional spatial modelling and computation

Interested in participating ?

Then send me an email at: pers@nada.kth.se


Required reading:

Books

1. Worboys, M.: GIS - a Computing Perspective. Taylor & Francis 1995. Ch. 3-6.
2. Schneider, M.: Spatial Data Types for Database Systems. Ph D thesis, FernUniversität Hagen, 1995 (15 copies of the thesis will be available for purchase during the course).

Articles

1. E. Clementini, P. Di Felice, P. van Oosterom: A Small Set of Formal Topological Relationships Suitable for End-User Interaction. In: Abel and B. C. Ooi (eds), Advances in Spatial Databases. Lecture Notes in Computer Science 692. Springer Verlag 1993, pp. 277-295.
2. E. Clementini, P. Di Felice: Approximate Topological Relations. Int. J. Approximate Reasoning, Vol. , No. , 1997.
3. J. G. Stell, M. F. Worboys: The Algebraic Structure of Sets of Regions. To appear in Proc. COSIT '97.
4. M. Overmars: Teaching Computational Geometry. ftp://ftp.cs.ruu.nl/pub/RUU/CS/techreps/CS-1993/1993-34.ps.gz
5. D. T. Lee: Computational Geometry. ACM Computing Surveys, Vol. 28, No. 1, March 1996, pp. 27-31.
6. R. Tamassa: Data Structures. ACM Computing Surveys, Vol. 28, No. 1, March 1996, pp. 23-26.
7. E. M. Reingold: Basic Techniques for Design and Analysis of Algorithms. ACM Computing Surveys, Vol. 28, No. 1, March 1996, pp. 19-21.
8. De Floriani, E. Puppo, P. Magillo: Geometric Structures and Algorithms for Geographic Information Systems. Technical Report DISI-TR-97-08. Dipartimento di Informatica e Scienze dell'Informazione, Universita di Genova, June 1997.
9. L. De Floriani, E. Puppo, A Hierarchical Triangle-based Model for Terrain Description. In: A.U. Frank, I. Campari, U. Formentini (Eds.): Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, Lecture Notes in Computer Science, No. 639, Springer-Verlag, 1992, pp. 236-251.
10. M. Bertolotto, L. De Floriani, P. Marzano: A Unifying Framework for Multilevel Description of Spatial Data. In: A. U. Frank, W. Kuhn (Eds.): Spatial Information Theory: A Theoretical Basis for GIS, International Conference COSIT '95, Lecture Notes in Computer Science, Vol. 988, Springer, 1995, pp. 259-278.


Books suitable for additional reading:

1. de Berg, M., van Kreveld, M., Overmars, M., & Schwarzkopf, O.: Computational Geometry: Algorithms and Applications. Springer 1997.
2. O'Rourke, J.: Computational Geometry in C, Cambridge U. P. 1994.


WWW links:

Geometry in Action
C. G. in Cartography and Geographic Information Systems
Voronoi Diagrams in Geomatics
The Geometry Center
Computational Geometry
Polygonal and Polyhedral Geometry
Geometry
Geometric Modeling and Computer Graphics
Various pointers to C. G. information
Frequently asked questions in C. G.


Computational Geometry Libraries and Applications:

CGAL - Computational Geometry Algorithms Library
LEDA - Library of Efficient Datatypes and Algorithms
PlaNet - Planar Networks
MOSES - Knowledge based aerial image analysis
LoLA - Library of location algorithms

^ Up to Course 2D5345.