AUTOCLUST+: Automatic Clustering of Point-Data Sets in the Presence of Obstacles

Abstract

Wide spread clustering algorithms use the Euclidean distance to measure spatial proximity. However, obstacles in other GIS data-layers prevent traversing the straight path between two points. AUTOCLUST+ clusters points in the presence of obstacles based on Voronoi modeling and Delaunay Diagrams. The algorithm is free of user-supplied arguments and incorporates global and local variations. Thus, it detects high-quality clusters (clusters of arbitrary shapes, clusters of different densities, sparse clusters adjacent to high-density clusters, multiple bridges between clusters and closely located high-density clusters) without prior knowledge. Consequently, it successfully supports correlation analyses between layers (requiring high-quality clusters) and more general locational optimization problems in the presence of obstacles. All this within O(n log n+[m+R] log n) expected time, where n is the number of data points, m is the number of line-segments that determine the obstacles and R is the number of Delaunay edges intersecting some obstacles. A series of detailed performance evaluations illustrates the power of AUTOCLUST+ and confirms the virtues of our approach.