Maps are a very effective means of communicating spatial information. They contain a suitable selection of themes of real-world data, displayed using their outlines or symbology, and with a well-chosen collection of colors. Furthermore, maps contain textual information (annotation, labels) to show the names or meanings of the map objects displayed. There are many different types of maps. Best known are tourist and topographic maps, but there are many other types of maps too. They include statistical maps, choropleth maps, reachability maps, density maps, cartograms, and many more.

The design and drawing of maps is traditionally done by cartographers. But in the current digital era, computers play a large role in map design and construction too. Various laborsome tasks of cartographers can be taken over, at leat in part, by specialized algorithms. Furthermore, maps can be shown on-screen, which extends the visual possibilities of displaying spatial information. This has lead to interactive, dynamic, and animated maps, for example.

Typical research themes within automated cartography are:

• Where to place text on maps.
• How to select information and perform changes for cartographic generalization.
• How to perform label placement and cartographic generalization during (interactive) zooming.
• How to automatically construct cartograms, dot maps, schematic maps, etc.
• Which criteria and geemetric measures to use for map design and generalization.

In the SPIRIT project, a spatially-aware search engine will be built. This European project (EU-IST project no. IST-2001-35047) is a collaboration with Cardiff University, University of Hanover, University of Zurich, University of Sheffield, and IGN Paris. The search engine to be developed, also called SPIRIT, consists of an ontology with information on geographic locations, a term index (like any search engine), a spatial index, a user interface, and a relevance ranking component. At Utrecht University we develop the relevance ranking methods.

This project deals with geographic analysis, among which clustering and spatial interpolation with obstacles, spatio-temporal interpolation, anisotropy, and spatial and spatio-temporal data mining.

Automated Visualization of Traffic and Transportation is the name of a project funded by the dr.ir. Cornelis Lely Stichting. It deals with maps dedicated to visualizing network connections, flow, and transportation, and is carried out by Sergio Cabello. So far, research has concentrated on the automated construction of schematized maps. An applet showing an implementation of this research can be found here.

During the years 1996-2001, there has been a project on automated text placement on maps. The project was funded by NWO. Tycho Strijk studied various geometric approximation algorithms for label placement on maps. Steven van Dijk studied genetic algorithms to solve the combinatorial optimization problem involved in map labeling. A large bibliography papers on automated map labeling is maintained by Alexander Wolff and can be found here.

As the final master project, Tom Priester developed applets that visualize the continuous changes that are needed for on-screen zooming and generalizations. A description and the applets are available.

The following people are currently involved in this research area:

• Kevin Buchin (postdoc)
• Maike Buchin (postdoc)
• dr. Marc van Kreveld (leader)

• P.K. Agarwal, M. van Kreveld, and S. Suri. Label placement by maximum independent set in rectangles. TR Comput. Geom. Theory Appl., 11:209--218, 1998.
• M. van Kreveld, T. Strijk, and A. Wolff. Point labeling with sliding labels. TR Comput. Geom. Theory Appl., 13:21--47, 1999.
• T. Strijk and M. van Kreveld. Labeling a rectilinear map more efficiently. TR Inf. Proc. Lett., 69:25--30, 1999.
• T. Strijk and M. van Kreveld. Practical extensions of point labeling in the slider model. TR, GeoInformatica, 6:181-197.
• S. van Dijk, M. van Kreveld, T. Strijk, and A. Wolff. Towards an evaluation of quality for names placement methods. TR In Proc. 19th International Cartographic Conference (CD-ROM), 1999.
• Alexander Wolff, Lars Knipping, Marc van Kreveld, Tycho Strijk, and Pankaj K. Agarwal. A simple and efficient algorithm for high-quality line labeling. In Peter M. Atkinson and David J. Martin, editors, Innovations in GIS VII: GeoComputation, chapter 11, pages 147--159. Taylor & Francis, 2000.
• M. van Kreveld, R. van Oostrum, and J. Snoeyink. Efficient settlement selection for interactive display. In Proc. Auto-Carto 13: ACSM/ASPRS Annual Convention Technical Papers, pages 287--296, 1997.
• M. de Berg, M. van Kreveld, and S. Schirra. Topologically correct subdivision simplification using the bandwidth criterion. TR Cartography and GIS, 25:243--257, 1998.
• M. Jansen and M. van Kreveld. Evaluating the consistency of cartographic generalization. Paper. In T.K. Poiker and N. Chrisman, editors, Proc. 8th Int. Symp. on Spatial Data Handling, pages 668--678, 1998.
• M. van Kreveld and J. Peschier. On the automated generalization of road network maps. Paper. In Proc. 3rd Int. Conf. on GeoComputation (CD-rom), 1998.
• M. van Kreveld. Smooth generalization for continuous zooming. Paper. In Proc. 20th International Cartographic Conference, pages 2180--2185, 2001.
• J. Bose, S. Cabello, J. Gudmundsson, M. van Kreveld, and B. Speckmann. Area-preserving approximations of polygonal paths. Submitted.
• S. Cabello, M. de Berg, and M. van Kreveld. Schematization of networks. Comput. Geom. Theory & Appl. Accepted for publication. TR
• S. Cabello and M. van Kreveld. Approximation algorithms for aligning points. Algorithmica, 37:211-232, 2003. TR
• Steven van Dijk. Genetic Algorithms for Map Labeling. PhD thesis, Utrecht University, 2001.
• Steven van Dijk, Dirk Thierens, and Mark de Berg. Designing genetic algorithms to solve GIS-problems. In R. Krzanowski and J. Raper, editors, Spatial Evolutionary Modeling. Oxford University Press, 2001.
• Steven van Dijk, Dirk Thierens, and Mark de Berg. Scalability and efficiency of genetic algorithms for geometrical applications. In M. Schoenauer et al, editors, Lecture Notes in Computer Science, Volume 1917: Proceedings of the Parallel Problem Solving from Nature VI Conference, pages 683-692. Springer-Verlag, 2000.
• Steven van Dijk, Dirk Thierens, and Mark de Berg. Using genetic algorithms for solving hard problems in GIS. Technical Report TR-2000-32, Utrecht University, 2000.
• Steven van Dijk, Dirk Thierens, and Mark de Berg. On the design of genetic algorithms for geographical applications. In W. Banzhaf et al, editors, Proceedings of the Genetic and Evolutionary Computation Conference, pages 188-195. Morgan-Kaufmann, 1999.
• Steven van Dijk, Dirk Thierens, and Mark de Berg. Robust genetic algorithms for high quality map labeling. Technical Report TR-1998-41, Utrecht University, 1998.
• M. van Kreveld and I. Reinbacher. Good NEWS: Partitioning a simple polygon by compass directions. Int. J. Comput. Geom. and Appl. Invited to special issue, accepted for publication. TR
• M. van Kreveld, I. Reinbacher, A. Arampatzis, and R. van Zwol. Distributed ranking methods for geographic information retrieval. In Developments of Spatial Data Handling, Peter Fisher, editor, Springer, 2004, pages 231-243.
• M. van Kreveld and B. Speckmann, 2002. Cutting a country for smallest square fit. In Proc. ISAAC'02, volume 2518 of Lecture Notes in Computer Science, pages 91-102. Springer.

Last Changed: Nov 1, 2005