Title: A Hybrid Algorithm for Terrain Simplification

Terrain simplification problem is one of fundamental problems in computational geometry and it has many applications in other fields such as geometric information systems, computer graphics, image processing. Terrain is commonly defined by a set of n points in three dimension space. Major goal of terrain simplification problem is removing some points of one terrain so that maximum error of simplified surface is a certain threshold. There are two optimization goals for this problem: (1) min-k, where for a given error threshold , the goal is to find a simplification with the minimum number of points for which the error is that most , and (2) min-, where for a given number n, the goal is to find a simplification of at most m points that has the minimum simplification error. Simplification problem is NP-hard in optimal case.In this paper we present a hybrid algorithm for terrain simplification that performs in three phases. First, terrain is divided to some clusters, then any cluster is simplified independently and finally, the simplified clusters are merged. Our algorithm solves the problem in. The proposed algorithm is implemented and verified by experiments.