Efficient code for second order analysis of events on a linear network

Abstract

We describe efficient algorithms and open-source code for the second-order statistical analysis of point events on a linear network. Typical summary statistics are adaptations of Ripley’s K-function and the pair correlation function to the case of a linear network, with distance measured by the shortest path in the network. Simple implementations consume substantial time and memory. For an efficient implementation, the data structure representing the network must be economical in its use of memory, but must also enable rapid searches to be made. We have developed such an efficient implementation in C with an R interface written as an extension to the R package spatstat. The algorithms handle realistic large networks, as we demonstrate using a database of all road accidents recorded in Western Australia.