Quick Search:

uzh logo
Browse by:

Zurich Open Repository and Archive

Maintenance: Tuesday, July the 26th 2016, 07:00-10:00

ZORA's new graphical user interface will be relaunched (For further infos watch out slideshow ZORA: Neues Look & Feel). There will be short interrupts on ZORA Service between 07:00am and 10:00 am. Please be patient.

Permanent URL to this publication: http://dx.doi.org/10.5167/uzh-6451

Yan, H; Weibel, Robert (2008). An algorithm for point cluster generalization based on the Voronoi diagram. Computers & Geosciences, 34(8):939-954.

[img] PDF - Registered users only
View at publisher


This paper presents an algorithm for point cluster generalization. Four types of information, i.e. statistical, thematic, topological, and metric information are considered, and measures are selected to describe corresponding types of information quantitatively in the algorithm, i.e. the number of points for statistical information, the importance value for thematic information, the Voronoi neighbors for topological information, and the distribution range and relative local density for metric information. Based on these measures, an algorithm for point cluster generalization is developed. Firstly, point clusters are triangulated and a border polygon of the point clusters is obtained. By the border polygon, some pseudo points are added to the original point clusters to form a new point set and a range polygon that encloses all original points is constructed. Secondly, the Voronoi polygons of the new point set are computed in order to obtain the so-called relative
local density of each point. Further, the selection probability of each point is computed using its relative local density and importance value, and then mark those will-be-deleted points as ‘deleted’ according to their selection probabilities and Voronoi neighboring relations. Thirdly, if the number of retained points does not satisfy that computed by the Radical Law, physically delete the points marked as ‘deleted’ forming a new point set, and the second step is repeated; else physically deleted pseudo points and the points marked as ‘deleted’, and the generalized point clusters are achieved. Owing to the use of the Voronoi diagram the algorithm is parameter free and fully automatic. As our experiments show, it can be used in the generalization of point features arranged in clusters such as thematic dot maps and control points on cartographic maps.


17 citations in Web of Science®
30 citations in Scopus®
Google Scholar™



5 downloads since deposited on 02 Dec 2008
0 downloads since 12 months

Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Geography
Dewey Decimal Classification:910 Geography & travel
Uncontrolled Keywords:Point clusters; Map generalization; Measures; Algorithms; Voronoi diagrams
Date:August 2008
Deposited On:02 Dec 2008 11:07
Last Modified:05 Apr 2016 12:37
Publisher DOI:10.1016/j.cageo.2007.07.008

Users (please log in): suggest update or correction for this item

Repository Staff Only: item control page