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.

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.