Segmentation is one popular method for geospatial data mining. We propose efficient and effective sequential-scan algorithms for higher-order Voronoi diagram districting. We extend the distance transform algorithm to include complex primitives (point, line, and area), Minkowski metrics, different weights and obstacles for higher-order Voronoi diagrams. The algorithm implementation is explained along with efficiencies and error. Finally, a case study based on trade area modeling is described to demonstrate the advantages of our proposed algorithms.
Segmentation is one approach to build topology (Chen et al., 2010, Hanafizadeh and Mirzazadeh, 2011, Lee et al., 2012 and Seng and Lai, 2010) and it is one popular method for geospatial data mining. Generalized Voronoi Diagrams (GVDs) are generalizations of the ordinary Voronoi diagram to various metrics, different weights, in the presence of obstacles, complex data types (point, line and area), and higher order. Recently, Lee and Torpelund-Bruin (2012) proposed an efficient and effective GVD algorithms for use in geospatial data mining. However, the model is limited to the first order and is not able to capture higher order scenarios. In many real business settings, people are more interested in the second or third nearest object. For instance, patients are interested in the second nearest hospital when the first nearest hospital is fully occupied or closed. This article extends (Lee & Torpelund-Bruin, 2012) to implement truly flexible higher-order Voronoi diagrams (HOVD) for map segmentation and geospatial data mining.
HOVD have been studied by many researchers and found useful for a variety of applications when k number of points are considered for partitioning ( Boots and South, 1997, Lee and Gahegan, 2002, Lee and Lee, 2007, Lin and Kung, 2001 and Xie et al., 2007). Recently, interest has been growing into exploiting HOVD for the partitioning of geospatial information for GIS applications ( Pinliang, 2008). However, current HOVD modeling techniques are limited because of the complexity of the traditional vector-based algorithms used ( Lee & Lee, 2009). This encompasses generators being typically limited to points in the absence of obstacles, the underlying metric limited to the Euclidean metric and weights of generators assumed to be invariant. For accurate geospatial analysis, a robust and versatile method is required to model the diverse and various components associated with real world geospatial analysis. This has lead to the exploration of efficient raster-based methods for GVD.
Due to advances in Web 2.0 technologies and the prevalence of Web Map Service (WMS) such as Google Map (http://maps.google.com), Google Earth (http://earth.google.com), NASA World Wind (http://worldwind.arc.nasa.gov), and Open Street Map (http://www.openstreetmap.org), districting Web maps through raster-based GVD is of emergence. In this article, we propose efficient and effective sequential-scan algorithms for HOVD districting. We extend the distance transform algorithm (Shih & Wu, 2004) to include complex primitives (point, line, and area), Minkowski metrics, different weights and obstacles for HOVD. The algorithm implementation is explained along with efficiencies and error. These new algorithms can be used to enhance accuracy for order-k and ordered order-k queries in various geospatial applications. To demonstrate the advantages of our proposed algorithms within an application, a case study based on trade area modeling is described.
Section 2 begins with a brief explanation of the properties of Voronoi diagrams. Section 3 describes current raster-based techniques for distance transforms and their application to Voronoi diagrams. Section 4 describes the reasoning of the sequential-scan algorithm for higher-order analysis. Sections 4.2.2 and 4.3.2 describe the implementation of the generalized higher-order algorithms for no obstacles and obstacles in the plane respectively. Sections 6 and 7 reflect the efficiency and error of the described algorithms. Section 8 describes a case study demonstrating how the algorithms can be applied for various applications and studies. Finally, Section 9 reflects on the study and future work.
