CSIS Discussion Paper #26

CSIS Discussion Paper #26

The K-Function Method on a Network
and its Computational Implementation
Atsuyuki OKABE* and Ikuho YAMADA**

April 20, 2000

* Center for Spatial Information Science, University of Tokyo** Department of Urban Engineering, University of Tokyo
7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656 Japan
E-mail: atsu@ua.t.u-tokyo.ac.jp, iku@ua.t.u-tokyo.ac.jp

Acknowledgement
The authors thank Yukio Sadahiro and Kei-ichi Okunuki for their valuable comments on earlier versions of this paper. We acknowledge the support of the Ministryof Education Grant No.1480092.
This paper is a completely revised version of CSIS Discussion Paper Series No.23,“The K-Function Methods on a Network and their Computational Method” written
in Japanese.

Abstract
This paper proposes two statistical methods, called the network K-function
method and the network cross K-function method, for analyzing the distributionof points on a network. The former method is used for testing the hypothesisthat points are uniformly and independently distributed over a network. The latter method is used for testing the hypothesis that points of one kind and pointsof another kind are independently distributed over a network. The paper first derives the equations of these functions. Second, these equations are implemented
in computational procedures. Third, the computational orders of these procedures
are obtained: the order of the K-function method is O(n2Q log nQ ) and that for the
network cross K-function is O(nQ log nQ ), where nQ is the number of nodes of a
network.

1

Introduction
Among many kinds of statistical methods that examine the distribution of points

on a plane, probably the K-function method (Ripley 1981) is one of the most frequently used methods in the literature (Cressie 1991; Fotheringham and Rogerson
1994; Bailey and Gatrell 1995). Like most statistical methods, the K-function
method assumes a continuous plane with the Euclidean distance. Recently, however, Miller (1994) criticized the limitation of this assumption in conjunction withan increasing demand for detailed spatial analysis enhanced by geographic information systems (GIS). Actually this limitation is problematic when we apply theordinary K-function method to a fairly small district. For instance, consider thelocation analysis of fast-food stands in a downtown. The stands cannot be locatedfreely in the downtown, but they are located along streets. Consumers cannot fly
to the stands, but they have to access to the stands through streets. The Euclidean
distance is quite different from the route distance there. In addition to the discrepancy between the Euclidean plane and an actual space, there is a great demand
for marketing in a small area with detailed spatial features, called micro-marketing(Buxton 1992). This discrepancy and the demand for micro-marketing require thedevelopment of a K-function method defined on a discrete network.
At present, however, this development is difficult because of the following reasons.
First, the ordinary K-function method assumes an infinite homogeneous plane, but
it is difficult to consider an infinite homogeneous network; a given network is almost
always irregular and it is difficult to expand this irregular network to an infinite
irregular network. Second, a method for computing a K-function on a network ismuch more complicated than the ordinary K-function method, because a network is
usually inhomogeneous (note that the ordinary K-function assumes a homogeneousplane). Third, it is difficult to obtain and manage digital network data. Recently, the1

progress in GIS has overcome the third difficulty, but the first and second difficulties
still remain unsolved. The objective of this paper is to overcome these difficulties
and propose a practical K-function method defined on a network.
Although we hardly find a K-function method in the literature, we can find somestatistical and/or computational methods for analyzing point objects on a network.
Miller (1994), Okabe and Kitamura (1996), and Okunuki and Okabe (1998) formulate the Huff model on a network. Okabe et al. (1995) formulate the nearest neighbordistance method on a network. Miller (1999) proposes the space-time accessibility
measure defined on a network. We elaborate those computational methods andapply them to the K-function method on a network.
The paper consists of five sections including this introductory section. In thenext section, i.e. Section 2, we formulate the K-function method on a network. Thismethod is used for testing the null hypothesis that points are uniformly distributed
over a network, or testing no spatial interaction among the points. In Section 3
we formulate the cross K-function method on a network. This method is used
for testing the null hypothesis that points of one kind are uniformly distributed
regardless of the locations of points of another kind. For example, this method isuseful to examine whether or not the distribution of fast-food stands is affected by
the locations of subway stations. In Section 4, we develop a computational method
for the network K-functions. We close this paper in Section 5, summarizing the
major results.

2

The network K-function method
First let us fix a general setting. We consider a finite connected planar network,

N = N (L, Q), consisting of a set of links, L = {L1 , . . . , LnL }, and a set of nodes,
Q = {q1 , . . . , qnQ }. We denote the whole links by LT (i.e. LT =2

SnL

k=1 Lk ) and thetotal length of LT by lT . Note that both ends of a link in L are nodes in Q and nolinks are connected except at nodes of Q. In the real world, the network N may
represent a network of streets in a city where a node in Q represents an intersectionof streets and a link in L represents a street segment between two intersections. We
measure the distance between two points on LT of N by the length of the shortest
path between them, which we call the network distance. Note that we may refer toa network distance simply as a distance when a network is understood.
We next consider a set of n objects, such as fast-food stands, which can be
regarded as a set of points, P = {p1 , . . . , pn }, and assume that the points of P areon the links LT of N . This implies that the size of the objects is negligibly small
relative to the size of the network, and the objects are located along streets (imagine
fast-food stands facing streets).
Now we assume that points of P are probabilistically distributed according to
the uniform distribution over LT of N , i.e.,f (p) =



1



, p ∈ LT ,

lT




 0,

(1)

p∈
/ LT ,

where p is a point of P . Under this assumption, the probability of a point in P being
placed on a subset, LS , of LT is proportional to the length, lS , of LS . Thus, theprobability, Pr[N(LS ) = nS ], that the number, N(LS ), of points of P being placedon LS is exactly nS is given by
Pr [N(LS ) = nS ] = n CnS

lS
lT

! nS

lS
1−
lT

( ) (

!n−nS

)

,

(2)

where n CnS = n!/ (nS ! (n − nS )!). Since this is a binomial distribution, the stochastic point process of P where points of P are distributed according to the uniform
distribution of equation (1) is called the binomial point process (Ripley 1981).
The assumption of the binomial point process implies the hypothesis that objects3represented by P (say fast-food stands) are uniformly and independently distributed
over the street network N . Thus if this hypothesis is not accepted, we may inferthat the fast-food stands are spatially interacting and dependent each other; as aresult, they form a non-uniform pattern. The stands may tend to be close together,or they may tend to keep away from each other. In the former case, we say that the
fast-food stands are clustering; in the latter case, we say that they are repelling.
Under the assumption of the binomial point process, we define a function, K(t),by

K(t) =

the number of points of P within

1 
,
E

ω 
network distance t of a point pi of P

(3)

where E(·) is the expected value with respect to i = 1, . . . , n (pi ∈ P ) where P follows
the binomial point process, and ω is the density of points of P , i.e. ω = n/lT . We
call this function K(t) the network K-function for the binomial point process.
Since the points of P are distributed according to the binomial point process,all points in P are independently and uniformly distributed over LT , and hence theabove definition is equivalent toK(t) = the number of points of P within


,


1 
E
ω 

(4)

network distance t of a point p on LT

where E(·) is the expected value with respect to all possible locations of p over LT .
Let Lp (t) be the subset of LT where the network distance between p and any pointon Lp (t) is less than or equal to t; lp (t) be the length of Lp (t). Since ω lp (t) indicatesthe expected number of points of P on Lp (t) under the assumption of the binomial
point process, we can write K(t) as
Z

1 1
K(t) =·
ω lp (t) dp
ω lT p∈LT
1 Z=
lp (t) dp ,lT p∈LT4(5)

where dp implies the integration of p along LT .
Now suppose that we observe n points of P on LT (consequently, P is fixed),
and let Lpi (t) be a subset of LT where the network distance between pi and any
point on Lpi (t) is less than or equal to t. From equation (3), the K-function for thisobserved data set, K̂(t), is written asn
1 1X
K̂(t) =·
(the number of points of P within network distance t of pi )
ω n i=1

=

n
1 1X
·
(the number of points of P on Lpi (t)) .
ω n i=1(6)

Since ω = n/lT , we can rewrite K̂(t) asK̂(t) =nlT X
(the number of points of P on Lpi (t)) .
n2 i=1(7)

We call the function K̂(t) the observed network K-function for a given set P .
Once we obtain the observed network K-function K̂(t) and the network Kfunction for the binomial point process K(t), we can examine whether or not theobserved points are distributed according to the binomial point process. If K̂(t) >K(t), we may infer that the points of P are clustering; if K̂(t) < K(t), the pointsof P are repelling.
We make one remark on the boundary effect. In general, we should distinguish
two types of the boundary effect when we use a spatial statistic dealing with the
distribution of points in a finite area, R. The first type boundary effect occurs
when points outside R are neglected. The second type boundary effect occurs whena statistic which assumes a point process on an infinite area (such as the Poisson
point process) is applied to a finite area R. The second type boundary effect occurs
even when points are not distributed outside R. Any spatial statistic cannot correct
the first type boundary effect unless points outside R are given. The second typeboundary effect may be or may not be corrected. For example, consider the ordinary5

K-function method defined byK(t) =

the number of points of P within Euclidean 
1 
.
E

ω 
distance t of pi of P on an infinite area

(8)

Under the assumption that the points of P are distributed according to the binomial
point process, K(t) is given byK(t) ==

the number of points of P within

1 

E


ω
Euclidean distance t of p on an infinite area1
(ωπt2) = πt2 .
ω(9)If this K-function method is applied to a finite area R, the second type boundary
effect occurs, because the circle with radius t may not be included in R. To correct
this boundary effect, Bailey and Gatrell (1995) adopt an adjustment factor whichconverts the finite area R to an infinite area. This modification is possible because
the ordinary K-function method assumes an infinite homogeneous area. In the caseof the network K-function method, however, we cannot adopt such an adjustment
factor, because, first, a network is not homogeneous; second, it is difficult to consider
an infinite homogeneous network. To overcome these difficulties, we need a methodthat directly deals with a finite inhomogeneous network. In the network K-function
defined above, we consider this method in terms of lp (t) in theory. If this function
lp (t) is practically computable, the proposed network K-function method would be
useful in practice. We discuss this computational implementation in Section 4.

3

The network cross K-function method
In the preceding section, we dealt with one kind of points P . In this section wedeal with two kinds of points, Pa = {pa1 , . . . , pana } and Pb = {pb1 , . . . , pbnb }, placedon LT of N . For instance, Pa may be a set of fast-food stands and Pb may be a set
6

of subway stations. We are concerned with whether or not the locations of subway
stations affect the distribution of fast-food stands. To examine this effect, we makea null hypothesis that points Pa are distributed according to the binomial point
process. This assumption implies that fast-food stands Pa are uniformly distributed
over LT regardless the locations of subway stations Pb . Note that we make noassumption on the distribution of points Pb . If the above hypothesis is rejected, we
may infer that the locations of subway stations Pb affect the distribution of fast-foodstands Pa .
Extending the network K-function defined in Section 2, we define a new function,
K ba (t), for two kinds of points Pa and Pb byK ba (t) = the number of points of Pa within

1
,
E


ωa
network distance t of a point pbi of Pb(10)

where E(·) is the expected value with respect to i = 1, . . . , nb (pbi ∈ Pb ) where
Pb follows the binomial point process, and ωa is the density of points of Pa , i.e.
ωa = na /lT . We call this function K ba (t) the network cross K-function of Pa relative
to Pb for the binomial point process.
Let Lpbi (t) be the subset of LT where the distance between pbi and any pointon Lpbi (t) is less than or equal to t, and lpbi (t) be the length of Lpbi (t). Under theassumption of the binomial point process, ωa lpbi (t) gives the expected number ofpoints of Pa on Lpbi (t). Thus we can rewrite K ba (t) as
K ba (t) =

nb
1 1 X
·
ωa lpbi (t)ωa nb i=1nb
1 X=
lp (t).
nb i=1 bi(11)Suppose that we observe the locations of na points of Pa and that of nb points of
Pb on LT . For these observed data sets, we write the cross K-function corresponding7

to equation (10) asnb
1 1 X
K̂ (t) =·(the number of points of Pa on Lpbi (t)) .
ωa nb i=1ba

(12)Since ωa = na /lT , we can rewrite K̂ ba (t) asnblT XK̂ (t) =(the number of points of Pa on Lpbi (t)) .
na nb i=1ba

(13)

We call the function K̂ ba (t) the observed network cross K-function of Pa relative toPb .
Once we obtain the observed network cross K-function K̂ ba (t) and the network
cross K-function for the binomial point process K ba (t), we can examine whether or
not the observed points Pa are distributed according to the binomial point process.
If K̂ ba (t) > K ba (t), we can infer that the points of Pa are clustering around thepoints of Pb ; if K̂ ba (t) < K ba (t), the points of Pa are repelling the points of Pb .

Computational methods for the network K-functions

4

In the preceding sections we theoretically obtained the equations of the network
K-function and the network cross K-function, but those equations are implicit for
actual computation. In this section, we wish to develop their computational methods
by extending the methods proposed by Okabe et al. (1995), Okabe and Kitamura(1996), and Okunuki and Okabe (1998). Since a computational method for the
network K-function is an extension of that for the network cross K-function, we
first show the latter method and next the former method.

4.1

A computational method for the network cross K-function

We notice from equation (11) that K ba (t) is computable if the length lpbi (t) of
Lpbi (t) is computable for all points in Pb = {pb1 , . . . , pbnb }. In this subsection, we
8develop a procedure for computing lpbi (t) (illustrative examples in Figure 1 would
be helpful to understand this procedure).
In Figure 1(a), Lpbi (t) (the subset of L where the distance from pbi to any point on
Lpbi (t) is less than or equal to t) is indicated by the thick gray-colored lines. Recallingthat a network distance is the length of the shortest path between points, we noticethat a set of the gray lines Lpbi (t) forms part of the ‘extended’ shortest path tree
rooted at pbi , and lpbi (t) is given by the length of this gray tree. This observationsuggests a strategy for computing lpbi (t): first, we construct the ‘extended’ shortest
path tree; second, we obtain Lpbi (t); third, we measure the length of Lpbi (t), which
gives lpbi (t).
To obtain the ‘extended’ shortest path tree, we first insert a point pbi of Pb in
the network N and regard it as a node (the black circle in Figure 1(b)). Second, weconstruct the shortest path tree rooted at pbi (the thick black lines in Figure 1(b)).
On each link that is not included in this shortest path tree (the thin lines in Figure
1 (b)), there exists one point to which two shortest paths from pbi through the two
end points of the link have the same distance (the stars in Figure 1(b)). We call thispoint a break point generated by pbi . Third, we cut links at all break points, andput nodes on both cut ends (the white circles in Figure 1(c)). We call the resulting
nodes break-point nodes generated by pbi . Let N +i = N +i (L+i , Q+i ) be the network
modified through the above procedure, where L+i denotes a set of resulting refined
links, and Q+i denotes a set of nodes consisting of Q and the resulting break-point
nodes. Since the distance from the root pbi to every node in Q+i is known by theextended shortest path tree, we can easily obtain Lpbi (t).
We next measure the length lpbi (t) of Lpbi (t) (the gray lines in Figure 1(d)). To
this end, we treat Lpbi (t) link by link; we measure the length of Lpbi (t) for each link,
and sum up those lengths. To be explicit, let gjpbi (t) be the length of Lj ∩ Lpbi (t),9i.e. the length of part of a link Lj that is included in Lpbi (t). Then we can obtain
lpbi (t) fromn+i

lpbi (t) =

L
X

j=1

gjpbi (t) ,

(14)

+i
where n+i
L is the number of links in L .

The form of gjpbi (t) varies according to the relation between Lj and Lpbi (t). Let
lj be the length of Lj , and qcj and qrj be the end points of Lj where d(pbi , qcj ) <d(pbi , qrj ) (for simplicity, we denote d(pbi , qcj ) by dcj , and d(pbi , qrj ) by drj ). When
Lj is not included in Lj (t), i.e. Lj ∩ Lpbi (t) = ∅, it is obvious that gjpbi (t) = 0(for example, L1 in Figure 1(d)). When Lj is completely included in Lpbi (t), i.e.
Lj ∩ Lpbi (t) = Lj , it is plain to see that gjpbi (t) = lj (L2 in Figure 1(d)). When Lj
is partly included in Lpbi (t), gjpbi (t) is given by the length of Lj ∩ Lpbi (t), i.e. t − dcj(L3 in Figure 1(d)). In terms of these equations, gjpbi (t) is written as

gjpbi (t) =











0 ≤ t < dcj ,0,t − dcj ,dcj ≤ t < drj ,







 drj − dcj (= lj ) , drj ≤ t < ∞ .

(15)

Therefore K ba (t) is explicitly written as
n+i

nb X
L
1 X
K ba (t) =g pbi (t) .
nb i=1 j=1 j(16)

Having established the computational procedure, let us consider the computational order of this procedure. Almost all of the computations in the above procedure
have a linear order with respect to the number of links, but the computation of theshortest path tree has more order than that. Fredman and Tarjan (1984) showthat the computational order of constructing the shortest path tree rooted at one
node of a network is O(nQ log nQ ), where nQ is the number of nodes of the network.
In the above procedure, we construct the shortest path tree rooted at each point10

of Pb = {pb1 , . . . , pbnb }, and hence the total computational order is O(nb nQ log nQ )(note that the number of nodes in Q+i has the same order of nQ ). In usual applications, the number of points of Pb (say, subway stations) is much smaller than thatof Q (the nodes of the network), and so the computational order is dominated byO(nQ log nQ ).

4.2

A computational method for the network K-function

We notice from equation (5) that K(t) is computable if the length lp (t) of Lp (t) is
computable for all possible locations of p over LT of N . In theory, a computational
method for lp (t) is similar to that for lpbi (t) of the network cross K-function shownin the above subsection, but the former method becomes much more complicatedin practical computation. The reason is that in the cross K-function method, we
compute lpbi (t) for a finite number of points in Pb (i.e. pb1 , . . . , pbnb ), but in the
K-function method, we have to compute lp (t) for every point p on LT (infinite). We
carry out this computation by moving p continuously along all links in LT .
In Figure 2, the cross mark indicates the location of a point p on N , and thethick gray lines indicate Lp (t). As p moves along links, the form of Lp (t) changes(compare Figure 2(a), (b), and (c)), but we notice that the topological relation ofnodes in Lp (t) does not change while p moves along a certain range (for example,
Figure 2(a) and (b) have the same topological relation of nodes in Lp (t); the topology
remains the same while p moves between q1 and q2 ). Since this topological invarianceproperty makes computation tractable, we first decompose LT into refined links insuch a way that the topology of Lp (t) remains the same when p moves along eachof the refined links. Once such refined links are obtained, we can obtain the length,
lp (t|s), of Lp (t) as a function of a parameter value, s, indicating the distance of pfrom one end point of the refined link on which p moves. Averaging the resulting
11

function lp (t|s) with respect to s and all refined links, we obtain the expected lengthof Lp (t) for every point p in LT . This procedure consists of the following four steps(illustrative examples in Figure 3, 4, and 5 would be helpful to understand thesesteps). Note that in the following, the network N is assume to have no parallel links(but relaxation of this assumption is simple).
Step 1: refinement of links
First, we insert the break-points, Q∗ , generated by all nodes of Q = {q1 , . . . , qnQ }in L (the white circles in Figure 3(b)). We call the resulting refined links the firstorder refined links and denote them by L∗ = {L∗1 , . . . , L∗n∗L }, where n∗L is the numberof links in L∗ .
Now we choose an arbitrary first order refined link, L∗k , in L∗ , and suppose thatp moves along this link from one end point, qkA , to the other end point, qkB (inFigure 3(c), the link q1∗ q2∗ is chosen as L∗k ). Further, we refine the first order refined
links by inserting the break-point nodes, Q∗k , generated by qkA and qkB (the graycircles in Figure 3(c)). We call the resulting refined links the second order refined∗k∗klinks with respect to L∗k and denote them by L∗k = {L∗k
1 , . . . , Ln∗k }, where nL is theLnumber of links in L∗k . In general, indices of links in L∗ and those of links in L∗kare different, but for notational convenience, we use the same index k for the linkon which p moves (i.e. L∗k and L∗kk indicate the same link).
Step 2: classification of the second order refined links
Having obtained the second order refined links L∗k , we now classify them into
four types.
∗k
Let lj∗k be the length of the link L∗kj (j = 1, . . . , nL ), and s be the network

distance between p and qkA (0 ≤ s ≤ lk∗k ). As p moves along L∗kk from qkA to qkB(i.e. s varies from 0 to lk∗k ), each break point generated by p moves along a link in

12

L∗k . We call the traces of these break points the trace links of p. Note that eachtrace link is one of the second order refined links, and that the length of each trace
link is equal to lk∗k . In an illustrative example shown in Figure 3(d), as p moves fromq1∗ to q2∗ , the break points, p0(1) and p0(2) , generated by p move from q1∗k to q4 and fromq3 to q2∗k , respectively. Thus, q1∗k q4 and q3 q2∗k are trace links of p.
Now we classify the second order refined links into four types (see Figure 4):
Type 1 is L∗kk , on which p moves, and Type 2 is the trace links of p. If we separate
links of Type 1 and Type 2 from the network, the remaining network has two trees
rooted at qkA and qkB , respectively. Type 3 links are the links forming the tree
rooted at qkA , and Type 4 links are those forming the tree rooted at qkB .
Step 3: formulation of the length of Lj k ∩ Lp (t) for each type of links
We consider the length, gjk (t|s), of L∗kj ∩ Lp (t), i.e. the length of part of a linkL∗kj where the distance between p and any point on that part is less than or equal
to t for each type of links. Illustrative examples are shown in Figure 5, where thecross mark indicates the location of p, the thick gray lines indicate Lp (t), and thethick black lines on Lp (t) indicate L∗kj ∩ Lp (t). Note that qcj and qrj are the end
points of L∗kj where d(qkA , qcj ) < d(qkA , qrj ), and dcj and drj indicate d(qkA , qcj ) andd(qkA , qrj ), respectively.
Type 1: L∗kk (i.e. the link on which p moves)∗kSuppose that p is located on the left half of L∗kk i.e. 0 ≤ s ≤ lk /2. If 0 ≤ t < s,k∗kthen Lp (t) is completely included in L∗kk , and so gk (t|s) = 2t. If s ≤ t < (lk − s)(see Figure 5(a)), the right half of Lp (t) is completely included in L∗kk , but the left
half of Lp (t) is beyond qkA . Thus gkk (t|s) = t + s. If (lk∗k − s) ≤ t < ∞, thenk∗kL∗kk is completely included in Lp (t), and so gk (t|s) = lk . In the same way, we canformulate gkk (t|s) when p is located on the right half of L∗kk . Summing up the above,
we can write gkk (t|s) as follows:13l∗k0≤s≤ k2

gkk (t|s) =lk∗k< s ≤ lk∗k2

gkk (t|s) =











0≤t<s,

2t ,t + s , s ≤ t < lk∗k − s ,







 lk∗k ,lk∗k − s ≤ t < ∞ ,











(17)

0 ≤ t < lk∗k − s ,2t ,t + (lk∗k − s) , lk∗k − s ≤ t < s ,








lk∗k ,
s≤t<∞.

(18)

Type 2: the trace links of p (see Figure 5(b))
In this case, a shortest path from p to a point on a trace link may go througheither qkA or qkB according to the value of s. Thus we can write gjk (t|s) for links ofType 2 in the same way as in Type 1.
l∗k0≤s≤ k
2















0 ≤ t < dcj + s ,0,t − (dcj + s) ,dcj + s ≤ t < lk∗k + dcj − s ,
2t − (2dcj + lk∗k ) ,







∗k


lk∗k + dcj − s ≤ t < lk∗k − dcj ,gjk (t|s) =


lk ,

(19)

lk∗k − dcj ≤ t < ∞ ,lk∗k< s ≤ lk∗k2gjk (t|s) =




0,
0 ≤ t < dcj + lk∗k − s ,








 t − (dcj + lk∗k − s) , dcj + lk∗k − s ≤ t < dcj + s ,
2t − (2dcj + lk∗k ) ,








l∗k ,
k

(20)

dcj + s ≤ t < lk∗k − dcjlk∗k − dcj ≤ t < ∞ .

In a similar fashion, we can formulate gjk (t|s) for links of Type 3 and Type 4 asfollows.
14

Type 3: the links included in the tree rooted at qkA (see Figure 5(c))










gjk (t|s) = 

0 ≤ t < dcj + s ,0,t − (d + s) ,d +s≤t<d +s ,

cj
cj
rj






 drj − dcj (= lj∗k ) , drj + s ≤ t < ∞ .

(21)Type 4: the links included in the tree rooted at qkB (see Figure 5(d))










gjk (t|s) = 

0 ≤ t < dcj − s ,0,t − (d − s) ,d −s ≤t < d −s ,

cj
cj
rj






 drj − dcj (= lj∗k ) , drj − s ≤ t < ∞ .

(22)

Step 4: integration of gjk (t|s)
As we showed above, we can formulate gjk (t|s) for each second order refined link∗kL∗kj with respect to an arbitrary location of p on Lk . Thus we can obtain the value,

lpk (t|s), of lp (t) when p is located at s on L∗k
k as
∗k

nL
X

lpk (t|s) =j=1

gjk (t|s) .

(23)

Therefore, the expected value, E(lp (t)), of lp (t) for all possible locations of p over
LT is given by

n∗

Z

L
lk∗
1 X
E(lp (t)) =lpk (t|s) ds ,lT k=1 0(24)

and K(t) in equation (5) can be rewritten as
K(t) =

1lT

Z

lp (t) dp ,

p∈LT
n∗

Z

L
lk∗k
1 X
=
lk (t|s) ds .
lT k=1 0 p(25)

We end up this subsection with the computational order of the above procedure.
In the above procedure, we have to construct the shortest path tree rooted at eachnode of Q = {q1 , . . . , qnQ } and Q∗ (note that the number of nodes in Q∗ has at15most the same order of nQ ). This computational order is O(n2Q log nQ ). Just likethe computational procedure in the preceding subsection, other computations in theabove procedure have a linear order with respect to the number of links, so that the
total computational order of the above procedure is dominated by O(n2Q log nQ ).

5

Conclusions
The ordinary K-function method, which is often used in spatial statistics, as-sumes a homogeneous plane with the Euclidean distance. This assumption is hardly
acceptable when we analyze the distribution of points in a fairly small district where
the Euclidean distance is quite different from the shortest path distance on a street
network and points are distributed along streets. To overcome this difficulty, thispaper proposed the network K-funciton method and the network corss K-funciton
method.
The network K-function method, defined by equations (5) and (7), is designed fortesting the hypothesis that points are uniformly and independently distributed overa network (for instance, this statistic is useful for testing whether or not fast-foodstands are uniformly distributed over streets in a downtown).
The network cross K-function method, defined by equations (11) and (13), is
designed for testing the hypothesis that points of one kind are independently distributed on a network regardless of the locations of points of another kind (forinstance, this statistics is useful for testing whether or not fast-food stands tend togather around bus stops in a downtown).
These methods become practical by the computational methods shown in Section
4. The computational order of the network K-function method and that of the
network cross K-function method are O(n2Q log nQ ) and O(nQ log nQ ), respectively,
where nQ is the number of nodes of the network.
16

We expect that these K-function methods provide a powerful tool for spatial
analysis in a detailed geographical space with a street network, in particular, formicro-marketing.

Reference
Bailey, T.C., and Gatrell, A.C. (1995) Interactive Spatial Data Analysis, Harlow:
Longman.
Buxton, T. (1992) GIS Expected to Micromarketing Challenge, GIS World, Vol.5,
No.1, pp.70-72.
Cressie, N.A. (1993) Statistics for Spatial Data, Chichester: John Wiley.
Fotheringham, S., and Rogerson, P. (Editor)(1994) Spatial Analysis and GIS (Technical Issues in Geographic Information Systems), London: Taylor & Francis.
Fredman, M.L., and Tarjan, R.E. (1984) Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. Proceedings of the 25th Annual IEEE
Symposium on Foundation of Computer Science, Singer Island, Florida, pp.338346.
Miller, H.J. (1993) GIS and the Geometry of Facility Location Problems, GIS/LIS’93
Proceedings, pp.530-539.
Miller, H.J. (1994) Market Area Delimination within Networks Using Geographic
Information Systems, Geographical Systems, Vol.1, No.2, pp.157-173.
Miller, H.J. (1999) Measuring space-time accessibility benefits within transportation networks: Basic theory and computational methods, Geographical Analysis,
Vol.31, No. , pp.187-212.
Okabe, A., and Fujii, A. (1984) The Statistical Analysis through a Computational
Method of a Distribution of Points in Relation to Its Surrounding Network, Environment and Planning A, Vol.16, pp.107-114.
17

Okabe, A., Yomono, H. and Kitamura, M. (1995) Statistical Analysis of the Distribution of Points on a Network, Geographical Analysis, Vol.27, No. 2, pp.152-175.
Okabe, A., and Kitamura, M. (1996) A Computational Method for Market Area
Analysis on a Network, Geographical Analysis, Vol.28, No.4, pp.330-349.
Okunuki, K., and Okabe, A. (1998) A computational method for optimizing thelocation of a store on a continuum of a network when users’ choice behavior
follows the Huff model, Discussion Paper, Center for Spatial Information Scienceat the University of Tokyo, No.19.
Ripley, D. (1981) Spatial Statistics, Chichester, John Wiley.
Upton, G., and Fingleton, B. (1985) Spatial Data Analysis by Example: Volume 1:
Point Pattern and Quantitative Data, New York, John Wiley
Yomono, H. (1993) A Computational Method for Market Area Analysis on a Network, Theory and Applications of GIS, Vol.1, pp.47-56.

Figure captions
Figure 1: A computational method for the network cross K-function(a) the subset Lpbi (t), (b) break points generated by pbi ,(c)break-point nodes generated by pbi , (d)subset Lpbi (t)Figure 2: Topological relation of nodes
Figure 3: Refinement of links(a) an original network, (b) first order refined links,(c) second order refined links, (d) trace links of p
Figure 4: Types of Links
Figure 5: Computation of gjk (t|s)(a) Type 1, (b) Type2, (c) Type 3, (d) Type 418

Lpbi (t)break point

pbi

pbi
break point

(a)

(b)

Lpbi (t)

q2+i
q1+i
pbi

L1
pbi

q1
q3+i

q2

q4+i

(c)

L3

L2

(d)

Figure 1: A computational method for the netw ork cross K-function

q5

q5
q4

q4
Lx(t)

Lx(t)

q1

(a)

q5

q4

p

q2

q3

q1

q2

p

(b)

Lx(t)

q3

q1

(c)

Figure 2: Topological relation of nodes

19

p

q2

q3

q3

q3
q*8
q*7

q4

q4
q*5

q*6

q*4

q*3

(a)

q2

q1

(b)

q1

q*1

q3

q*2 q2q3p'(2)q*8=q*k2

q*8=q*k2
q*7

q*7

q4

q4
q*k1

p
q1

q*1
=qkA

(c)

p
q*2 q2
=qkB

q1

(d)

Figure 3: Refinement of links

Type 2Type 4

Type 3

p
qkA

p'(1)
q*k1

qkB

Type 1Figure 4: Types of links

20

q*1
=qkA

q*2
q2
=qkB

Lj*k

drj
qcj
t

qrj

t
t

dcj

p
s

t

Lk*k

qkA

qkB

qkA

(a)

(b)

qkB

p

s

qrj

drj
qcj

Lj*k
Lj*k

qrj

t

t

qkA

s

p

qkA

qkB

s

p

drj

qkB

qcj
dcj

dcj

(c)

(d)

Figure 5: Computation of gjk(t|s)

21