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
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
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)
Rodrigo I. Silveira (PhD student)
under the supervision of
dr. Marc van Kreveld.
For more information contact
Contact: Marc van Kreveld