September 28 – October 3 , 2003, Dagstuhl Seminar 03401

Computational Cartography and Spatial Modelling


Monika Sester (Leibniz Universität Hannover, DE)
Jack Snoeyink (University of North Carolina at Chapel Hill, US)
Peter van Oosterom (TU Delft, NL)
Michael Worboys (University of Maine, US)

For support, please contact

Dagstuhl Service Team


List of Participants
Dagstuhl's Impact: Documents available


The Dagstuhl seminar on ‘computational cartography and spatial modelling’ is the fourth in a series of seminars bringing computer scientists and spatial scientist together. This started with the first seminar (then called Computational Cartography) where Computational Geometers and Cartographers did meet and discuss their problems and potential solutions. With the third seminar, the multidisciplinary aspect has become even larger by adding ‘Spatial Modelling’ part was added to the scope. Scientist and developers with a broader geo-science background on the one hand (geography, geodesy,…) and a broader computer science background on the other hand (modelling, DBMS,…) were added to the multidisciplinary group of participants. This fourth seminar, without changing the title, became even more multidisciplinary as the spatial and temporal aspects of mobile computing (including topics such as location-based services and sensor networks) were included in the program. The group of participants was diverse both w.r.t. to their academic discipline and their professional background. Researchers and developers from within industry, government, and universities (senior and young) shared their latest topics, problems, doubts, and investigations.


The technological advances of the recent past, for example, increasing graphics capabilities, multimedia technology, multimodal interaction possibilities, distributed computing, the Internet, wireless communication, new sensors, and efficient geo-data collection techniques, have lead to many new possibilities for interaction with and visualization of spatial data. These advances are currently hampered by lack of suitable algorithms as well as limited understanding of the possibilities of human interaction with spatial data. In the spatial modelling and analysis domain, the field is lacking an integrated approach to deal with (3D) space, time, attributes and their interrelations. Multi-scale issues complicate matters even more, because certain patterns or processes only show up or play a role at specific scales. Most studies so far have concentrated on at most two of the issues: (3D) space, time, attribute, and scale. During the seminar several presentations tried to address more of these issues at the same time; e.g. 3D generalization (scale) based on the classification and attributes of the object (and task/context of the user). As stated above, this year’s seminar also covered the application to portable computing: e.g. location based services and mobile GIS, where low-bandwidth, limited display capabilities require new thinking on aspects such as computational support and human computer interaction. Furthermore, cognitive aspects, context awareness as well as user preferences and privacy issues have to be respected and integrated.


The presentations were organized into a number of sessions with related topics. Some of the presentations covered a single aspect of the theme for the seminar and others addressed several aspects within one presentation. Both types of presentations were very interesting and contained the statement of (new) problems and solutions in a single or multidisciplinary context. The presentations focused on:

  1. computational geometry (3D Hilbert curves, new dynamic spatial indexing, definition of valid polygons, equal polygon subdivision, conveyor belt-assisted path planning, etc.),
  2. geographic reasoning (mathematical concepts, matroids, cognitive aspects, geo-processes),
  3. database and topology issues (topology rules, persistent topology storage),
  4. 3D models (TIN/TEN-based, reconstruction/manipulation terrains and objects; e.g. buildings including roofs),
  5. generalization (also in 3D, buildings), and
  6. mobile/kinematic GIS (sensor networks, LBS, privacy aspects, context-aware map agents).

Due to the efforts of both the presenters and the audience, the disciplinary boundaries were crossed many times and this resulted in refreshing discussions. This was directly after the presentations, but also during the breaks in the pleasant environment of the Schloss Dagstuhl, there was sufficient time to go into more detailed discussions. It has been a very fruitful meeting for all participants. The meeting place traditions (problems/ challenges sessions, ample time for questions and interactions between talks, environment: library, computer room, common rooms, etc.) indeed helped to break down barriers imposed by academic disciplines. Some of the new research results presented were obtained in collaborative projects (and cooperation’s) which started after the previous Dagstuhl seminar.

Outcomes include

  • A collection of abstracts, presentations (slides) and a number of papers surveying the current state of the art in this field and latest research initiatives.
  • Similar to the previous seminar on ‘Computational Cartography and Spatial Modeling’, it is expected that new partnerships and collaborations between multi-disciplinary groups (reinforced and established during the current seminar) will further advance this field with the inclusion of emerging topics.
  • Another important result of the seminar is the Open Problem List

The program (after several dynamic changes):

Monday 29 Sept 2003:

  • Peter van Oosterom, TU Delft, Netherlands:
    Polygons: the unstable foundation of spatial modeling
  • Lars Harrie, Lund University, Sweden:
    Real-Time Data Generalization and Integration for Location-based services
  • Patrick Lauble, Universität Zürich, Switzerland:
    Of Pigheads, Followers and Trendsetters – Matching Motion Patterns in Groups of Moving Point Objects
  • Jack Snoeyink, UNC Chapel Hill, USA,
    Generating Hilbert curves for spatial ordering in higher dimensions
  • Lars Kulik, University of Maine, USA:
    Linearized Terrain Representation
  • Siva Ravada, Oracle Corp.-Nashua, USA:
    Persistent Topology Management in Oracle Spatial

Tuesday 30 Sept 2003:

  • Stephan Nebicker, FHBB - Fachhochschule Basel, Switzerland:
    Design Issues in 3D GIS – Lessons from the DILAS Project
  • Edward Verbree, TU Delft, Netherlands:
    Surface Representations by Delaunay triangulations
  • Alexander Wolff, Universität Karlsruhe, Germany:
    Shortest Path Maps and Minibus Networks (helping tourists to reach quickly the Empire State Building)
  • Stephan Winter, University of Melbourne, Australia (was TU Wien):
    Salience of spatial features
  • Wilko Quak, TU Delft, Netherlands:
    (Temporal) topologic modelling inside a GIS
  • Silvia Nittel, University of Maine, Orono, USA:
    Sensor networks from a GIS perspective
  • Lars Arge, Duke University, USA:
    B kd-trees: a dynamic scalable kd-tree

Wednesday 1 Oct 2003:

  • John Stell, University of Leeds, UK:
    Oriented Matroids as a Foundation for Geographic Space
  • Marc van Kreveld, Utrecht University, Netherlands:
    On the Education of GIS Algorithm Design
  • Mike Worboys, University of Maine, Orono, USA:
    Modeling time in geo-phenomena
  • Jörg Siebeck, Universität Bonn, Germany:
    Managing spatio-temporal objects in databases: representation and query concepts
  • Klaus Brenner, Universität Hannover, Germany:
    Roof reconstruction from laser scanner data and additional sources
  • Jan van Roessel, ESRI, USA:
    Rule evaluation for topology evaluation
  • Takeshi Shirabe, TU Wien, Austria:
    An Explicit Model of Contiguity
  • Iris Reinbacher, Utrecht University, Netherlands:
    Good news: partitioning polygons by compass directions
  • Rebecca Tse, Hong Kong Polytechnic Univ., China:
    3D Terrain models
  • Chris Gold, Hong Kong Polytechnic Univ., China:
    Applications of Kinetic Voronoi Diagrams
  • Volker Steinhage, Universität Bonn, Germany:
    You can’t see what you do not know

Thursday 2 Oct 2003:

  • Monika Sester, Universität Hannover, Germany:
    Generalization: from 2D to 3D
  • Nicolas Regnauld, Ordnance Survey, U.K.:
    Research in building amalgamation
  • Matt Duckham, University of Maine, Orono, USA:
    Imprecise Navigation (privacy and indiscernibility in location-aware systems)
  • Jörg-Rudiger Sack, Carleton University, Ottawa:
    Intelligent Map Agents – Geographic Information Services
  • Martin Heller, Universität Zürich, Switzerland:
    Large (multi-scale) triangle based terrain models

Friday morning

  • breakout sessions

Dagstuhl Seminar Series


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.