Problem Definition:
Please consider join the mailing list to directly receive updates related to the competition.
Geometry
generalization is a well known concept in the field of cartography
(http://en.wikipedia.org/wiki/Cartographic_generalization).
This concept is used in producing maps with less detail according to
map scale. The algorithms used for geometry generalization usually
concentrate on the techniques for simplifying individual geometry
objects. When these algorithms are applied to a map, the result might
not be what the user expects.
Consider
a map that displays a set of state boundaries at a very detailed
level. Some states share boundaries with other states and the areas
of the states do not overlap with each other. In addition, let’s
add a set of cities to the map. Some of these cities might be very
close to the state boundaries. Now let us consider a simplified
version of the same map. If geometry generalization algorithms are
applied to each state boundary independently, the resulting map might
not be accurate. For example, the simplified state boundaries might
not align with each other exactly as they did before the
simplification. Some of the cities that are very close to the state
boundaries might now be in a different state if the simplified state
boundary now falls on the other side of the point used to represent
the city.
To
facilitate this type of map simplification, it is often desirable to
break the state boundaries into different line geometries so that all
shared boundaries are represented as unique line geometries. These
lines are then simplified and connected back together to form the
state boundaries. With this approach, the state boundaries will still
preserve the nonoverlapping property they had before the boundary is
simplified. But this itself does not guarantee that the cities still
maintain their relative position with respect to their state
boundaries.
This
year’s SIG Spatial competition explores this map generalization
problem and challenges the students to come up with novel solutions
for this very useful problem. The scope of the problem is limited to
allow the students to develop a meaningful solution in a short amount
of time.
Problem Definition
INPUT: A set of linear geometries that bound polygonal regions and a set of constraining points.
OBJECTIVE: Simplify the linear geometries such that the relationship between the constraining points and linear geometries before and after the simplification does not change. In addition, the topological relationships between the original set of input linear geometries does not change after the simplification.
Description: Geometry generalization is a well known area and there are two main algorithms ((i) Peucker Algorithm and (ii) Visvalingam_Whyatt Algorithm). These techniques can be applied to linear and polygonal geometries to produce generalized geometries. The same techniques can also be applied to produce generalized maps. In map generalization one of the difficult problems is to maintain the topological consistency between adjacent polygonal regions during the simplification process. This is explained with the help of the following figures.
Consider
a set of 6 lines: L1 .. L6 arranged as in Figure 1.
Figure
2 shows a valid simplification of these 6 lines. Note that the end
points of each of the lines do not move. Only some of the
intermediate points of the lines are deleted.
Next,
Figure 3 shows an invalid simplification of these lines.
Next
example in Figure 4 shows input of 6 lines with 5 control points.
A
valid simplification for this input is shown in Figure 5.
Note
that, P1 forces line L1 not to be simplified further and P5 forces L4
not to be simplified further. Figure 6 shows an invalid
simplification of the input shown in Figure 4.
P1
changes position with respect to line L1, so it is not a valid
simplification. Similarly, point P5 changes position with respect to
line L4.
Assumptions
about the data and simplification process
 Data is assumed to be in Cartesian space.
 Linear geometries do not have selfintersections.
 Linear geometries do not intersect with other linear geometries except at end points.
 The constraining points do not intersect any of the linear geometries.
 Number of lines will vary for each test.
 Number of points will vary for each test.
 The line generalization algorithm is expected to delete some of the input points to generalize the lines. It is not expected to add vertices that are not part of the input.
 The number of vertices in the generalized line are less than or equal to the number of vertices in the original line geometry.
 The line generalization algorithm should not change the end points of the input line geometries. That is, it can remove any intermediate vertices except the end points. This preserves the original end point coincidences of the input line geometries.
Evaluation Rules
 The time to process all the input data will be the main criterion for the evaluation of the solution. So the solution with the best rate (points reduced per minute) is the winner.
 Each line will be assigned a score that is equal to the number of points reduced compared to the original geometry for that line.
 The accuracy of the result is also considered. If a line is simplified, but it violates the topological constraints of the input, the simplification for that line will not be considered. That is, even if x number of vertices are deleted from that line, the score for that line will be zero.
 The program should be able to take a parameter that specifies the number of points to be removed from the input.

We
will evaluate the input program with different values for this
parameter. Final score will be averaged over all the different runs.
Input Data Format
The
first section of the input will describe the input line geometries in
GML 2.1.1 format. The format will be an ID, followed by the GML for
the line. The second section of the input will describe the input
point geometries in GML 2.1.1. format. The format will be an ID,
followed by the GML for the point.
Output
Data Format
Output
should be the set of simplified line geometries along with their IDs.
The point geometries do not appear in the output.