Voronoi diagram and spatial clustering in the presence of obstacles

Zuocheng Wang; Lixia Xue; Yongshu Li; Linlin Wang; Xuewang Zhang

doi:10.1117/12.658211

4 January 2006 Voronoi diagram and spatial clustering in the presence of obstacles

Zuocheng Wang, Lixia Xue, Yongshu Li, Linlin Wang, Xuewang Zhang

Proceedings Volume 5985, International Conference on Space Information Technology; 59853T (2006) https://doi.org/10.1117/12.658211
Event: International Conference on Space information Technology, 2005, Wuhan, China

Abstract

Clustering in spatial data mining is to group similar objects based on their distance, connectivity, or their relative density in space. Clustering algorithms typically use the Euclidean distance. In the real world, there exist many physical obstacles such as rivers, lakes and highways, and their presence may affect the result of clustering substantially. In this paper, we study the problem of clustering in the presence of obstacles and propose spatial clustering by Voronoi distance in Voronoi diagram (Thiessen polygon). Voronoi diagram has lateral spatial adjacency character. Based on it, we can express the spatial lateral adjacency relation conveniently and solve the problem derived from spatial clustering in the presence of obstacles. The method has three steps. First, building the Voronoi diagram in the presence of obstacles. Second, defining the Voronoi distance. Based on Voronoi diagram, we propose the Voronoi distance. Giving two spatial objects, P_i and P_j, The Voronoi distance is defined that the minimum object Voronoi regions number between P_i and P_j in the Voronoi diagram. Third, we propose Following-Obstacle-Algorithm (FOA). FOA includes three steps: the initializing step, the querying step and the pruning step. By FOA, we can get the Voronoi distance between any two objects. By Voronoi diagram and the FOA, the spatial clustering in the presence of obstacles can be accomplished conveniently, and more precisely. We conduct various performance studies to show that the method is both efficient and effective.

Citation Download Citation

Zuocheng Wang, Lixia Xue, Yongshu Li, Linlin Wang, and Xuewang Zhang "Voronoi diagram and spatial clustering in the presence of obstacles", Proc. SPIE 5985, International Conference on Space Information Technology, 59853T (4 January 2006); https://doi.org/10.1117/12.658211

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
6 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Data modeling

Analytical research

Bridges

Data mining

Gold

Mathematics

Civil engineering

Show All Keywords

Keywords/Phrases

Search In:

Publication Years