Spatial Analysis Along Networks

Atsuyuki Okabe, Graduate School of Engineering, University of TokyoProfessor Okabe has been studying statistical spatial analysis for 35 years, and specifically statistical spatial analysis on a network since 1995. One of the leading authorities in the area, he has published over 100 articles, in numerous international journals. He has also authored and edited four previous books.Kokichi Sugihara, Graduate School of Information Science and Technology, University of TokyoProfessor Sugihara has co-authored the book on Voronoi diagrams with A. Okabe. He is also an experienced author and lecturer.

“Students and researchers studying spatial statistics, spatial analysis, geography, GIS, OR, traffic accident analysis, criminology, retail marketing, facility management and ecology will benefit from this book.”  (Zentralblatt MATH, 1 May 2013)

• Preface AcknowledgementsChapter 1 Introduction1.1 What is network spatial analysis?1.1.1 Network events: events on and alongside networks1.1.2 Planar spatial analysis and its limitations1.1.3 Network spatial analysis and its salient features1.2 Review of studies of network events1.2.1 Snow’s study on cholera around Broad Street1.2.2 Traffic accidents1.2.3 Road-kills1.2.4 Street crimes1.2.5 Events on river networks and coastlines1.2.6 Other events on networks1.2.7 Events alongside networks1.3 Outline of the book1.3.1 Structure of chapters1.3.2 Questions solved by network spatial methods1.3.3 How to study this bookChapter 2 Modeling events on and alongside networks2.1 Modeling the real world2.1.1 Object-based model2.1.1.1 Spatial attributes2.1.1.2 Nonspatial attributes2.1.2 Field-based model2.1.3 Vector data model2.1.4 Raster data model2.2 Modeling networks2.2.1 Object-based model for networks2.2.1.1 Geometric networks2.2.1.2 Graph for a geometric network2.2.2 Field-based model for networks2.2.3 Data models for networks2.3 Modeling entities on and alongside networks2.3.1 Objects on network space2.3.2 Field functions on network space2.4 Stochastic processes on network space2.4.1 Object-based model for stochastic spatial events on network space2.4.2 Binomial point processes on network space2.4.3 Edge effects2.4.4 Uniform network transformationChapter 3 Basic computational methods for network spatial analysis3.1 Data structures for one-layer networks3.1.1 Planar networks3.1.2 Winged-edge data structures3.1.3 Efficient access and enumeration of local information3.1.4 Attribute data representation3.1.5 Local modifications of a network3.1.5.1 Inserting new nodes3.1.5.2 New nodes resulting from overlying two networks3.1.5.3 Deleting existing nodes3.2 Data Structures for nonplanar networks3.2.1 Multiple-layer networks3.2.2 General nonplanar networks3.3 Basic Geometric Computations3.3.1 Computational methods for line segments3.3.1.1 Right-turn test3.3.1.2 Intersection test for two line segments3.3.1.3 Enumeration of line segment intersections3.3.2 Time complexity as a measure of efficiency3.3.3 Computational methods for polygons3.3.3.1 Area of a polygon3.3.3.2 Center of gravity of a polygon3.3.3.3 Inclusion test of a point with respect to a polygon3.3.3.4 Polygon-line intersection3.3.3.5 Polygon intersection test3.3.3.6 Extraction of a subnetwork inside a polygon3.3.3.7 Set-theoretic computations3.3.3.8 Nearest point on the edges of a polygon from a point in the polygon3.3.3.9 Frontage interval3.4. Basic computational methods on networks3.4.1 Single-source shortest paths3.4.1.1 Network connectivity test3.4.1.2 Shortest-path tree3.4.1.3 Extended shortest-path tree3.4.1.4 All nodes within a prespecified distance3.4.1.5 Center of a network3.4.1.6 Heap data structure3.4.2 Shortest path between two nodes3.4.3 Minimum spanning tree on a network3.4.4 Monte Carlo simulation for generating random points on a networkChapter 4 Network Voronoi diagrams4.1 Ordinary network Voronoi diagram4.1.1 Planar versus network Voronoi diagrams4.1.2 Geometric properties of the ordinary network Voronoi diagram4.2 Generalized network Voronoi diagrams4.2.1 Directed network Voronoi diagram4.2.2 Weighted network Voronoi diagram4.2.3 k-th nearest point network Voronoi diagram4.2.4 Line and polygon network Voronoi diagram4.2.5 Point-set network Voronoi diagram4.3 Computational methods for network Voronoi diagrams4.3.1 Multi-start Dijkstra method4.3.2 Computational method for the ordinary network Voronoi diagram4.3.3 Computational method for the directed network Voronoi diagram4.3.4 Computational method for the weighted network Voronoi diagram4.3.5 Computational method for the -th nearest point network Voronoi diagram4.3.6 Computational method for the line and polygon network Voronoi diagrams4.3.7 Computational method for the point-set network Voronoi diagramChapter 5 Network nearest-neighbor distance methods5.1 Network auto nearest-neighbor distance method5.1.1 Network local auto nearest-neighbor distance method5.1.2 Network global auto nearest-neighbor distance method5.2 Network cross nearest-neighbor distance method5.2.1 Network local cross nearest-neighbor distance method5.2.2 Network global cross nearest-neighbor distance method5.3 Network nearest-neighbor distance method for lines5.4 Computational methods for network nearest-neighbor distance methods5.4.1 Computational methods for network auto nearest-neighbor distance methods5.4.1.1 Computational methods for network local auto nearest-neighbor distance method5.4.1.2 Computational methods for network global auto nearest-neighbor distance method5.4.2 Computational methods for network cross nearest-neighbor distance methods5.4.2.1 Computational methods for network local cross nearest-neighbor distance method5.4.2.2 Computational methods for network global cross nearest-neighbor distance methodChapter 6 Network K function methods6.1 Network auto K function methods6.1.1 Network local auto K function method6.1.2 Network global auto K function method6.2 Network cross K function methods6.2.1 Network local cross K function method6.2.2 Network global cross K function method6.2.3 Network global Voronoi cross K function method6.3 Network K function methods in relation to geometric characteristics of a network6.3.1 Relationship between the shortest-path distance and the Euclidean distance6.3.2 Network global auto K function in relation to the level-of-detail of a network6.4 Computational methods for the network K function methods6.4.1 Computational methods for the network auto K function methods6.4.1.1 Computational methods for the network local auto K function method6.4.1.2 Computational methods for the network global auto K functionmethod6.4.2 Computational methods for the network cross K function methods6.4.2.1 Computational methods for the network local auto K function method6.4.2.3 Computational methods for the network global cross K function method6.4.2.3 Computational methods for the network global Voronoi cross Kfunction methodChapter 7 Network spatial autocorrelation7.1 Classification of spatial autocorrelations7.2 Spatial randomness of the attribute values of network cells7.2.1 Permutation spatial randomness7.2.2 Normal variate spatial randomness7.3 Network Moran’s I statistics7.3.1 Network local Moran’s I statistic7.3.2 Network global Moran’s I statistic7.4 Computational methods for network Moran’s I statisticsChapter 8 Network point cluster analysis and clumping method8.1 Network point cluster analysis8.1.1 General hierarchical point cluster analysis8.1.2 Hierarchical point clustering methods with specific intercluster distances8.1.2.1 Network closest-pair point clustering method8.1.2.2Network farthest-pair point clustering method8.1.2.3 Network average-pair point clustering method8.1.2.4 Network point clustering methods with other interclaster distances8.2 Network clumping method8.2.1 Relation to network point cluster analysis8.2.2 Statistical test with respect to the number of clumps8.3 Computational methods for network point cluster analysis and clumping method8.3.1 General computational framework8.3.2 Computational methods for individual intercluster distances8.3.2.1 Computational methods for the network closest-pair point clusteringmethod8.3.2.1 Computational methods for the network farthest-pair point clusteringmethod8.3.2.3 Computational methods for the network average-pair point clusteringmethod8.3.3 Computational aspects of the network clumping methodChapter 9 Network point density estimation methods9.1 Network histograms9.1.1 Network cell histograms9.1.2 Network Voronoi cell histograms9.1.3 Network cell-count method9.2 Network kernel density estimation methods9.2.1 Network kernel functions9.2.2 Equal-split discontinuous kernel functions9.2.3 Equal-split continuous kernel functions9.3 Computational methods for network point density estimation9.3.1 Computational methods for network cell histograms with equal-length network cells9.3.2 Computational method for equal-split discontinuous kernel density functions9.3.3 Computational method for equal-split continuous kernel density functionsChapter 10 Network spatial interpolation10.1 Network inverse-distance weighting10.1.1 Concepts of neighborhoods on a network10.1.2 Network inverse-distance weighting predictor10.2 Network kriging10.2.1 Network kriging models10.2.2 Concepts of stationary processes on a network10.2.3 Network variogram models10.2.4 Network kriging predictors10.3 Computational methods for network spatial interpolation10.3.1 Computational methods for network inverse-distance weighing10.3.2 Computational methods for network krigingChapter 11 Network Huff model11.1 Concepts of the network Huff model11.1.1 Huff models11.1.2 Dominant market subnetworks11.1.3 Huff-based demand estimation11.1.4 Huff-based locational optimization11.2 Computational methods for the Huff-based demand estimation11.2.1 Shortest-path tree distance11.2.2 Choice probabilities in terms of shortest-path tree distances11.2.3 Analytical formula for the Huff-based demand estimation11.2.4 Computational tasks and their time complexities for the Huff-based demand estimation11.3 Computational methods for the Huff-based locational optimization11.3.1 Demand function for a newly entering store11.3.2 Topologically invariant shortest-path trees11.3.3 Topologically invariant link sets11.3.4 Numerical method for the Huff-based locational optimization11.3.5 Computational tasks and their time complexities for the Huff-based locational optimizationChapter 12 GIS-based tools for spatial analysis along networks and their application12.1 Preprocessing tools in SANET12.1.1 Tool for testing network connectedness12.1.2 Tool for assigning points to the nearest points on a network12.1.3 Tool for computing shortest-path distances between points12.1.4 Tool for generating random points on a network12.2 Statistical tools in SANET and their applications12.2.1 Tools for network Voronoi diagrams and their application12.2.2 Tools for network nearest neighbor distance methods and their application12.2.2.1 Network global auto nearest-neighbor distance method12.2.2.2 Network global cross nearest-neighbor distance method12.2.3 Tools for network K function methods and their application12.2.3.1 Network global auto K function method12.2.3.2 Network global cross K function method12.2.3.3 Network global Voronoi cross K function method12.2.3.4 Network local cross K function method12.2.4 Tools for network cluster analysis and their application12.2.5 Tools for network kernel density estimation methods and their application12.2.6 Tools for network spatial interpolation methods and their applicationReferencesIndex