First lecture in Room 4523 Plan 5, Lindstedtsv. 5. Following weeks: Room 1537 Plan 5, Lindstedtsv. 3

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.

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.

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.

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).

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.

2. O'Rourke, J.: Computational Geometry in C, Cambridge U. P. 1994.

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.

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*.