Geometric Optimization with Geometric Constraints

Contact: Marc van Kreveld

Computational geometry addresses algorithmic problems dealing with geometric (or, spatial) data. As in all areas within algorithms research, the goal is to develop provably efficient algorithms and data structures for such problems. Although the field has a fundamental focus, applications exist in all areas where spatial data is processed: computer graphics and virtual reality, geographic information systems (GIS), robotics, and CAD/CAM are some obvious examples. The motivation of nearly all problems studied in computational geometry comes from such application areas.

Algorithms for geometric optimization have many applications. They are studied both in the research area computational geometry, and in application areas like motion planning, computer graphics, and geographic information systems. In computational geometry, the focus is on the development of provably efficient algorithms for abstracted versions of the problem. These algorithms should compute the optimal solution, or be at most a provable factor off the optimum. Algorithms of the second type are called approximation algorithms. In application areas, the problems are less abstracted and the algorithms are more heuristical: no provable performance is given.

In this project we will extend the computational geometry focus by using less abstraction in the problems to be solved. This is achieved by addressing problems that have two or more geometric criteria, instead of only one. This is particularly important for applications in geographic information systems and cartography, which we will show below. In the project both fundamental and more applied multiple-criteria problems will be investigated.

To focus the research, three classes of multi-criteria problems are considered in subprojects. These classes contain the most important and varied problem types from the theoretical perspective. Furthermore, they have significant potential applications. The first subproject addresses point set placement problems in computational geometry. One criterion is that each point be placed in its region while optimizing another criterion. The second subproject addresses triangulations for terrain modeling. The third subproject addresses shape design and placement. The next section motivates these subprojects.


Point Placement. In this subproject we let go of the assumption that the given points are exactly at the given coordinates. Instead, they can be anywhere in their own, prespecified region. There are several reasons why such problems are of interest. We present three of them as examples.

  • Area estimation under data imprecision. Many data acquisition techniques only give approximate positions of points where an attribute is known. These points are then used to determine the outline of a region, for example a crop field. The precise area of the crop field cannot be determined, but it is important to be able to determine upper and lower bounds on the area. Similar problems arise in the estimation of an underground reservoir of crude oil, and the estimation of the length of a connection network.
  • Clustering under data imprecision. Clustering is one of the main techniques for point pattern analysis. This is a topic studied in spatial data mining research. The clusters found can be seriously affected by slight changes in the locations of the points to be clustered. It is important to determine what the possible clusters are under location imprecision.
  • Schematic map design. Schematic maps are often used for public transportation, like metro maps. It is a highly stylized form of mapping, where the stations are only shown at approximately correct positions. Connections are stylized to 1-link or 2-link paths that have one of four orientations. To allow for many 1-link paths, the number of alignments in the given orientations should be maximized. At the same time, stations may not be moved too much. The latter criterion can be modeled by keeping the points within a given region.

Nice Terrains. Terrains are often modeled by triangulations. In nearly all applications where triangulations are used, the triangles must have a “nice shape”. This is true for visualization, mesh generation, and terrain modeling. Very often, to triangulate a set of points, the Delaunay triangulation is used. It maximizes the smallest angle that is used in the triangles, over all possible triangulations. This is a good way to formalize nice shape. For terrain modeling, however, nice shape is only one of the criteria that a triangulation should have. We give two examples.

  • Slope fidelity in terrains. The Delaunay triangulation is a triangulation of a planar set of points. In terrain modeling, points have a third coordinate that must be taken into account, even though a triangulation of the xy-projections of the points is sought. Slope fidelity in terrains means that there are no abrupt changes in slope (except at known, specified break lines of the surface). A triangulation for a terrain should use triangles of nice shape and have slope fidelity.
  • Drainage in terrains. Natural terrains do not have many local minima, because these would be eroded away by water flow on the terrain. When constructing a triangulated model of a terrain, some of the local minima that arise are caused by the triangulation: another triangulation of the same points may not have these minima. Therefore, it is better to generate triangulated terrains that have nicely shaped triangles and few local minima. Other drainage characteristics that influence the terrain model are the drainage lines, which are often known separately. The problem is to build a terrain model that has these drainage lines in the bottom of valleys by choosing the correct triangulation, if it exists.

Shape Design and Placement. Shapes, or polygons, that satisfy various geometric criteria are needed in various situations. These polygons must often satisfy criteria like having a “reasonable shape” (because unreasonable shapes are not typical, although they may be optimal for some other criterion), or being recognizable (where a reference shape is assumed). These criteria can be formalized in several ways, and often different formalizations must be used in conjunction. A variety of applications exist:

  • Cartographic generalization. When a map is needed at a smaller scale than available in the map data, cartographic generalization is needed. Detail must be removed, more abstraction should be used, and sometimes, map features must be displaced to avoid visual collisions (coalescence). One of the types of change is merging two regions into one, like two forest areas. The new polygon must follow the two old polygons closely, as little non-forest area should be added as possible, but a natural shape must be generated. The polygon to be computed must therefore satisfy several criteria at once.
  • Delineating imprecise regions. In Web data mining, the Web is used a source of information which is often not completely reliable or correct. Web data mining can for instance be used to delineate non-formal geographic regions, like Northern France, or Het Groene Hart in The Netherlands. The extent of such regions is partly a matter of the conception of people. Delineation of such regions is important for geographic information retrieval, where an Internet user may ask a search engine for castles in the British Midlands. A polygon is needed to come close to the general idea of people, which implies it follows evidence at several locations, and it must have a reasonable shape.
  • Diagram placement on maps. Pie charts are often placed on maps to show information about regions in an administrative subdivision (countries, provinces). Pie charts must be easy to associate with their region, they may not intersect each other, and they should not overlap too much of the region borders.

The project will primarily be carried out by Maarten Löffler (PhD student) and Rodrigo I. Silveira (PhD student) under the supervision of dr. Marc van Kreveld.

For more information contact
Contact: Marc van Kreveld