Abstract A Bipolar Model for Region Simplification

In this paper we introduce an algorithm for simplifying a 2D discrete region. This algorithm is based on a bipolar model of regions. Given a discrete region, we cut its Voronoi diagram into two parts along the border of the region and each part is a tree. We use the two trees to respectively model the structures of a region and its complement, which is called the Bipolar Model. The simplification is done by trimming the two trees. The running time of the algorithm is O(n log n) and the space needed is O(n), where n is the number of points in the border of a region. Key words: line simplification, bipolar model, Voronoi diagram, Voronoi tree. 1