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 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 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.
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.
Introduction to concepts of two-dimensional spatial modelling and computation
Interested in participating ?
Then send me an email at: firstname.lastname@example.org
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).
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.
2. O'Rourke, J.: Computational Geometry in C, Cambridge U. P. 1994.
Geometry in Action
C. G. in Cartography and Geographic Information Systems
Voronoi Diagrams in Geomatics
The Geometry Center
Polygonal and Polyhedral 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.