Map generalization with constraints

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. Assumptions about the data and simplification process Data is assumed to be in Cartesian space. Linear geometries do not have self-intersections. 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.