%FIXME NY8_utm18 shapefile and NY_nb.gal to package
%\VignetteIndexEntry{Creating Neighbours}
%\VignetteDepends{}
%\VignetteKeywords{spatial}
%\VignettePackage{spdep}
\documentclass[a4paper,10pt]{article} 
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage[dvips]{graphicx,color}
\usepackage{times}
\usepackage{hyperref}
\usepackage{natbib}
\usepackage[english]{babel}
\usepackage{xspace}

\usepackage{Sweave}
\usepackage{mathptm}
\usepackage{natbib}

\setkeys{Gin}{width=0.95\textwidth}
\newcommand{\strong}[1]{{\normalfont\fontseries{b}\selectfont #1}}
\let\pkg=\strong
\RequirePackage{alltt}
\newenvironment{example}{\begin{alltt}}{\end{alltt}}
\newenvironment{smallexample}{\begin{alltt}\small}{\end{alltt}}
\newcommand{\code}[1]{\texttt{\small #1}}
\def\RR{\textsf{R}\xspace}
\def\SP{\texttt{S-PLUS}\xspace}
\def\SS{\texttt{S}\xspace}
\SweaveOpts{keep.source=FALSE}

\title{Creating Neighbours\footnote{This vignette formed pp. 239--251 of the first edition of Bivand, R. S.,
Pebesma, E. and G\'{o}mez-Rubio V. (2008) Applied Spatial Data Analysis with R,
Springer-Verlag, New York. It was retired from the second edition (2013) to
accommodate material on other topics, and is made available in this form
with the understanding of the publishers.}} 
\author{Roger Bivand} 

\begin{document} 

\maketitle 

<<echo=FALSE>>= 
owidth <- getOption("width")
options("width"=90)
ow <- getOption("warn")
options("warn"=-1)
.PngNo <- 0
@
<<label=figreset,echo=FALSE,eval=FALSE>>= 
.iwidth <- 5
.iheight <- 6
.ipointsize <- 12
@

<<echo=FALSE,results=hide>>= 
<<figreset>>
@

<<label=afig,echo=FALSE,eval=FALSE>>= 
.PngNo <- .PngNo + 1; file <- paste("Fig-bitmap-", .PngNo, ".pdf", sep="")
pdf(file=file, width = 6.5, height = 3.5, pointsize = 12, bg = "white")
opar <- par(mar=c(3,3,1,1)+0.1)
@
<<label=afigl,echo=FALSE,eval=FALSE>>= 
.PngNo <- .PngNo + 1; file <- paste("Fig-bitmap-", .PngNo, ".pdf", sep="")
pdf(file=file, width = 6.5, height = 3.5, pointsize = 12, bg = "white")
@
<<label=bfigl,echo=FALSE,eval=FALSE>>= 
.PngNo <- .PngNo + 1; file <- paste("Fig-bitmap-", .PngNo, ".pdf", sep="")
pdf(file=file, width = 6.5, height = 5, pointsize = 12, bg = "white")
@
<<label=bfig,echo=FALSE,eval=FALSE>>= 
.PngNo <- .PngNo + 1; file <- paste("Fig-bitmap-", .PngNo, ".pdf", sep="")
pdf(file=file, width = 6.5, height = 5, pointsize = 12, bg = "white")
opar <- par(mar=c(3,3,1,1)+0.1)
@

<<label=zfig,echo=FALSE,eval=FALSE>>=
par(opar)
dev.null <- dev.off()
cat("\\includegraphics[width=0.95\\textwidth]{", file, "}\n\n", sep="")
@
<<label=zfigl,echo=FALSE,eval=FALSE>>=
dev.null <- dev.off()
cat("\\includegraphics[width=0.95\\textwidth]{", file, "}\n\n", sep="")
@

\section{Introduction}

Creating spatial weights is a necessary step in using areal data,
perhaps just to check that there is no remaining spatial
patterning in residuals. The first step is to define which
relationships between observations are to be given a non-zero
weight, that is to choose the neighbour criterion to be used; the
second is to assign weights to the identified neighbour links.

The 281 census tract data set for eight central New
York State counties featured prominently in
\citet{WallerGotway:2004} will be used in many of the
examples,\footnote{The boundaries have been projected from
geographical coordinates to UTM zone~18.} supplemented with tract
boundaries derived from TIGER 1992 and distributed by
SEDAC/CIESIN. This file is not identical with the boundaries used
in the original source, but is very close and may be
re-distributed, unlike the version used in the book.
Starting from the census tract queen contiguities, where all touching
polygons are neighbours, used in \citet{WallerGotway:2004} and provided
as a DBF file on their website, a GAL format file has been created and
read into \RR.

\begin{footnotesize}
<<echo=TRUE>>= 
if (require(rgdal, quietly=TRUE)) {
  NY8 <- readOGR(system.file("shapes/NY8_utm18.shp", package="spData"))
} else {
  require(maptools, quietly=TRUE)
  NY8 <- readShapeSpatial(system.file("shapes/NY8_utm18.shp", package="spData"))
}
library(spdep)
NY_nb <- read.gal(system.file("weights/NY_nb.gal", package="spData"), region.id=row.names(NY8))
@
\end{footnotesize}

For
the sake of simplicity in showing how to create neighbour
objects, we work on a subset of the map consisting of the
census tracts within Syracuse, although the same principles apply
to the full data set. We retrieve the part of the neighbour list
in Syracuse using the \code{subset} method.

\begin{footnotesize}
<<echo=TRUE>>= 
Syracuse <- NY8[NY8$AREANAME == "Syracuse city",]
Sy0_nb <- subset(NY_nb, NY8$AREANAME == "Syracuse city")
summary(Sy0_nb)
@
\end{footnotesize}


\section{Creating Contiguity Neighbours}

We can create a copy of the same neighbours object for polygon
contiguities using the \code{poly2nb} function in \pkg{spdep}. It takes an
object extending the \code{SpatialPolygons} class as its first argument,
and using heuristics identifies polygons sharing boundary points as
neighbours. It also has a \code{snap} argument, to allow the shared
boundary points to be a short distance from one another.


\begin{footnotesize}
<<echo=TRUE>>= 
class(Syracuse)
Sy1_nb <- poly2nb(Syracuse)
isTRUE(all.equal(Sy0_nb, Sy1_nb, check.attributes=FALSE))
@
\end{footnotesize}


As we can see, creating the contiguity neighbours from the
\code{Syracuse} object reproduces the neighbours from
\citet{WallerGotway:2004}. Careful examination of
Fig.\,\ref{fig:NY_nb} shows, however, that the graph of
neighbours is not planar, since some neighbour links cross each
other.  By default, the contiguity condition is met when at least
one point on the boundary of one polygon is within the snap
distance of at least one point of its neighbour. This
relationship is given by the argument \code{queen=TRUE} by
analogy with movements on a chessboard. So when three or more
polygons meet at a single point, they all meet the contiguity
condition, giving rise to crossed links. If \code{queen=FALSE},
at least two boundary points must be within the snap distance of
each other, with the conventional name of a `rook' relationship.
Figure~\ref{fig:NB_queen} shows the crossed line differences that
arise when polygons touch only at a single point, compared to the
stricter rook criterion.


\begin{footnotesize}
<<echo=TRUE>>= 
Sy2_nb <- poly2nb(Syracuse, queen=FALSE)
isTRUE(all.equal(Sy0_nb, Sy2_nb, check.attributes=FALSE))
@
\end{footnotesize}


\begin{figure}[!t]
\centering
<<results=tex,echo=FALSE>>= 
.iwidth <- 6
.iheight <- 4.5
.ipointsize <- 10
<<afig>>
oopar <- par(mfrow=c(1,2), mar=c(3,3,1,1)+0.1)
plot(Syracuse, border="grey60")
plot(Sy0_nb, coordinates(Syracuse), add=TRUE, pch=19, cex=0.6)
text(bbox(Syracuse)[1,1], bbox(Syracuse)[2,2], labels="a)", cex=0.8)
plot(Syracuse, border="grey60")
plot(Sy0_nb, coordinates(Syracuse), add=TRUE, pch=19, cex=0.6)
plot(diffnb(Sy0_nb, Sy2_nb, verbose=FALSE), coordinates(Syracuse),
  add=TRUE, pch=".", cex=0.6, lwd=2)
text(bbox(Syracuse)[1,1], bbox(Syracuse)[2,2], labels="b)", cex=0.8)
par(oopar)
<<zfig>>
<<figreset>>
@ 
\caption{(\textbf{a})
Queen-style census tract contiguities, Syracuse; (\textbf{b})
Rook-style contiguity differences shown as thicker lines}
\label{fig:NB_queen}\vspace*{-6pt}
\end{figure}

If we have access to a GIS such as GRASS or ArcGIS\texttrademark,
we can export the \code{SpatialPolygonsDataFrame} object and use
the topology engine in the GIS to find contiguities in the graph
of polygon edges -- a shared edge will yield the same output as
the rook relationship.

This procedure does, however, depend on the topology of the set
of polygons being clean, which holds for this subset, but not for
the full eight-county data set. Not infrequently, there are small
artefacts, such as slivers where boundary lines intersect or
diverge by distances that cannot be seen on plots, but which
require intervention to keep the geometries and data correctly
associated. When these geometrical artefacts are present, the
topology is not clean, because unambiguous shared polygon
boundaries cannot be found in all cases; artefacts typically
arise when data collected for one purpose are combined with other
data or used for another purpose. Topologies are usually cleaned
in a GIS by `snapping' vertices closer than a threshold distance
together, removing artefacts -- for example, snapping across a
river channel where the correct boundary is the median line but
the input polygons stop at the channel banks on each side. The
\code{poly2nb} function does have a \code{snap} argument, which
may also be used when input data possess geometrical artefacts.

%FIXME
\begin{footnotesize}
<<echo=TRUE,results=hide,eval=FALSE>>= 
library(spgrass6)
writeVECT6(Syracuse, "SY0")
contig <- vect2neigh("SY0")
@
<<echo=FALSE,results=hide,eval=FALSE>>=
load("contig.RData")
@
<<echo=TRUE,eval=FALSE>>=
Sy3_nb <- sn2listw(contig)$neighbours
isTRUE(all.equal(Sy3_nb, Sy2_nb, check.attributes=FALSE))
@
\end{footnotesize}


Similar approaches may also be used to read
ArcGIS\texttrademark~coverage data by tallying the left neighbour
and right neighbour arc indices with the polygons in the data
set, using either \pkg{RArcInfo} or \pkg{rgdal}.

In our Syracuse case, there are no exclaves or `islands'
belonging to the data set, but not sharing boundary points within
the snap distance. If the number of polygons is moderate, the
missing neighbour links may be added interactively using the
\code{edit} method for \code{nb} objects, and displaying the
polygon background. The same method may be used for removing
links which, although contiguity exists, may be considered void,
such as across a mountain range.


\section{Creating Graph-Based Neighbours}

Continuing with irregularly located areal entities, it is
possible to choose a point to represent the polygon-support
entities. This is often the polygon centroid, which is not the
average of the coordinates in each dimension, but takes proper
care to weight the component triangles of the polygon by area. It
is also possible to use other points, or if data are available,
construct, for example population-weighted centroids. Once
representative points are available, the criteria for
neighbourhood can be extended from just contiguity to include
graph measures, distance thresholds, and $k$-nearest neighbours.

The most direct graph representation of neighbours is to make a
Delaunay triangulation of the points, shown in the first panel in
Fig.\,\ref{fig:NB_graph}. The neighbour relationships are defined
by the triangulation, which extends outwards to the convex hull
of the points and which is planar. Note that graph-based
representations construct the interpoint relationships based on
Euclidean distance, with no option to use Great Circle distances
for geographical coordinates. \hbox{Because} it joins distant points
around the convex hull, it may be worthwhile to thin the
triangulation as a Sphere of Influence (SOI) graph, removing
links that are relatively long. Points are SOI neighbours if
circles centred on the points, of radius equal to the points'
nearest neighbour distances, intersect in two places
\citep{avis+horton:1985}.\footnote{Functions for graph-based
neighbours were kindly contributed by Nicholas \hbox{Lewin-Koh.}}


\begin{footnotesize}
<<echo=TRUE>>=
coords <- coordinates(Syracuse)
IDs <- row.names(as(Syracuse, "data.frame"))
#FIXME library(tripack)
Sy4_nb <- tri2nb(coords, row.names=IDs)
if (require(rgeos, quietly=TRUE) && require(RANN, quietly=TRUE)) {
  Sy5_nb <- graph2nb(soi.graph(Sy4_nb, coords), row.names=IDs)
} else Sy5_nb <- NULL
Sy6_nb <- graph2nb(gabrielneigh(coords), row.names=IDs)
Sy7_nb <- graph2nb(relativeneigh(coords), row.names=IDs)
@
\end{footnotesize}

\begin{figure}[!t]
\centering
<<results=tex,echo=FALSE>>= 
.iwidth <- 5
.iheight <- 3.5
.ipointsize <- 10
<<afig>>
oopar <- par(mfrow=c(2,2), mar=c(1,1,1,1)+0.1)
plot(Syracuse, border="grey60")
plot(Sy4_nb, coords, add=TRUE, pch=".")
text(bbox(Syracuse)[1,1], bbox(Syracuse)[2,2], labels="a)", cex=0.8)
plot(Syracuse, border="grey60")
if (!is.null(Sy5_nb)) {
  plot(Sy5_nb, coords, add=TRUE, pch=".")
  text(bbox(Syracuse)[1,1], bbox(Syracuse)[2,2], labels="b)", cex=0.8)
}
plot(Syracuse, border="grey60")
plot(Sy6_nb, coords, add=TRUE, pch=".")
text(bbox(Syracuse)[1,1], bbox(Syracuse)[2,2], labels="c)", cex=0.8)
plot(Syracuse, border="grey60")
plot(Sy7_nb, coords, add=TRUE, pch=".")
text(bbox(Syracuse)[1,1], bbox(Syracuse)[2,2], labels="d)", cex=0.8)
par(oopar)
<<zfig>>
<<figreset>>
@ 
\caption{(\textbf{a})
Delauney triangulation neighbours; (\textbf{b}) Sphere of
influence neighbours (if available); (\textbf{c}) Gabriel graph neighbours;
(\textbf{d}) Relative graph neighbours} \label{fig:NB_graph}\vspace*{-12pt}
\end{figure}

Delaunay triangulation neighbours and SOI neighbours are
symmetric by design -- if $i$ is a neighbour of $j$, then $j$ is
a neighbour of $i$. The Gabriel graph is also a subgraph of the
Delaunay triangulation, retaining a different set of neighbours
\citep{matula+sokal:80}. It does not, however, guarantee
symmetry; the same applies to Relative graph neighbours
\citep{toussaint:80}. The \code{graph2nb} function takes a
\code{sym} argument to insert links to restore symmetry, but the
graphs then no longer exactly fulfil their neighbour criteria.
All the graph-based neighbour schemes always ensure that all
the points will have at least one neighbour. Subgraphs of the
full triangulation may also have more than one graph after
trimming. The functions \code{is.symmetric.nb} can be used to
check for symmetry, with argument \code{force=TRUE} if the
symmetry attribute is to be overridden, and \code{n.comp.nb}
reports the number of graph components and~the components to
which points belong (after enforcing symmetry, because the
algorithm assumes that the graph is not directed). When there are
more than one graph component, the matrix representation of the
spatial weights can become block-diagonal if observations are appropriately sorted.

\begin{footnotesize}
<<echo=TRUE>>= 
nb_l <- list(Triangulation=Sy4_nb, Gabriel=Sy6_nb,
  Relative=Sy7_nb)
if (!is.null(Sy5_nb)) nb_l <- c(nb_l, list(SOI=Sy5_nb))
sapply(nb_l, function(x) is.symmetric.nb(x, verbose=FALSE, force=TRUE))
sapply(nb_l, function(x) n.comp.nb(x)$nc)
@
\end{footnotesize}


\section{Distance-Based Neighbours}

An alternative method is to choose the $k$ nearest points as
neighbours -- this adapts across the study area, taking account
of differences in the densities of areal entities. Naturally, in
the overwhelming majority of cases, it leads to asymmetric
neighbours, but will ensure that all areas have $k$ neighbours.
The \code{knearneigh} returns an intermediate form converted to
an \code{nb} object by \code{knn2nb}; \code{knearneigh} can also
take a \code{longlat} argument to handle geographical
coordinates.


\begin{footnotesize}
<<echo=TRUE>>= 
Sy8_nb <- knn2nb(knearneigh(coords, k=1), row.names=IDs)
Sy9_nb <- knn2nb(knearneigh(coords, k=2), row.names=IDs)
Sy10_nb <- knn2nb(knearneigh(coords, k=4), row.names=IDs)
nb_l <- list(k1=Sy8_nb, k2=Sy9_nb, k4=Sy10_nb)
sapply(nb_l, function(x) is.symmetric.nb(x, verbose=FALSE, force=TRUE))
sapply(nb_l, function(x) n.comp.nb(x)$nc)
@
\end{footnotesize}

\begin{figure}[!t]
\centering
<<results=tex,echo=FALSE>>= 
.iwidth <- 5
.iheight <- 2.5
.ipointsize <- 10
<<afig>>
oopar <- par(mfrow=c(1,3), mar=c(1,1,1,1)+0.1)
plot(Syracuse, border="grey60")
plot(Sy8_nb, coords, add=TRUE, pch=".")
text(bbox(Syracuse)[1,1], bbox(Syracuse)[2,2], labels="a)", cex=0.8)
plot(Syracuse, border="grey60")
plot(Sy9_nb, coords, add=TRUE, pch=".")
text(bbox(Syracuse)[1,1], bbox(Syracuse)[2,2], labels="b)", cex=0.8)
plot(Syracuse, border="grey60")
plot(Sy10_nb, coords, add=TRUE, pch=".")
text(bbox(Syracuse)[1,1], bbox(Syracuse)[2,2], labels="c)", cex=0.8)
par(oopar)
<<zfig>>
<<figreset>>
@ 
\caption{(\textbf{a})
$k=1$ neighbours; (\textbf{b}) $k=2$ neighbours; (\textbf{c})
$k=4$ neighbours} \label{fig:NB_knn}
\end{figure}

Figure~\ref{fig:NB_knn} shows the neighbour relationships for $k
= 1, 2, 4$, with many components for $k=1$. If need be,
$k$-nearest neighbour objects can be made symmetrical using the
\code{make.sym.nb} function. The $k=1$ object is also useful in
finding the minimum distance at which all areas have a
distance-based neighbour. Using the \code{nbdists} function, we
can calculate a list of vectors of distances corresponding to the
neighbour object, here for first nearest neighbours. The greatest
value will be the minimum distance needed to make sure that all
the areas are linked to at least one neighbour. The
\code{dnearneigh} function is used to find neighbours with an
interpoint distance, with arguments \code{d1} and \code{d2}
setting the lower and upper distance bounds; it can also take a
\code{longlat} argument to handle geographical coordinates.


\begin{footnotesize}
<<echo=TRUE>>= 
dsts <- unlist(nbdists(Sy8_nb, coords))
summary(dsts)
max_1nn <- max(dsts)
max_1nn
Sy11_nb <- dnearneigh(coords, d1=0, d2=0.75*max_1nn, row.names=IDs)
Sy12_nb <- dnearneigh(coords, d1=0, d2=1*max_1nn, row.names=IDs)
Sy13_nb <- dnearneigh(coords, d1=0, d2=1.5*max_1nn, row.names=IDs)
nb_l <- list(d1=Sy11_nb, d2=Sy12_nb, d3=Sy13_nb)
sapply(nb_l, function(x) is.symmetric.nb(x, verbose=FALSE, force=TRUE))
sapply(nb_l, function(x) n.comp.nb(x)$nc)
@
\end{footnotesize}

\begin{figure}[!t]
\centering
<<results=tex,echo=FALSE>>= 
.iwidth <- 5
.iheight <- 2.5
.ipointsize <- 10
<<afig>>
oopar <- par(mfrow=c(1,3), mar=c(1,1,1,1)+0.1)
plot(Syracuse, border="grey60")
plot(Sy11_nb, coords, add=TRUE, pch=".")
text(bbox(Syracuse)[1,1], bbox(Syracuse)[2,2], labels="a)", cex=0.8)
plot(Syracuse, border="grey60")
plot(Sy12_nb, coords, add=TRUE, pch=".")
text(bbox(Syracuse)[1,1], bbox(Syracuse)[2,2], labels="b)", cex=0.8)
plot(Syracuse, border="grey60")
plot(Sy13_nb, coords, add=TRUE, pch=".")
text(bbox(Syracuse)[1,1], bbox(Syracuse)[2,2], labels="c)", cex=0.8)
par(oopar)
<<zfig>>
<<figreset>>
@ 
\caption{(\textbf{a})
Neighbours within 1,158\,m; (\textbf{b})  neighbours within 1,545\,m;
(\textbf{c}) neighbours within 2,317\,m} \label{fig:NB_dnn}
\end{figure}

\begin{figure}[!t]
\centering
<<results=tex,echo=FALSE>>= 
.iwidth <- 5
.iheight <- 2.5
.ipointsize <- 10
<<afig>>
oopar <- par(mfrow=c(1,3), mar=c(1,1,1,1)+0.1)
plot(Syracuse, border="grey60")
plot(Sy11_nb, coords, add=TRUE, pch=".")
text(bbox(Syracuse)[1,1], bbox(Syracuse)[2,2], labels="a)", cex=0.8)
plot(Syracuse, border="grey60")
plot(Sy12_nb, coords, add=TRUE, pch=".")
text(bbox(Syracuse)[1,1], bbox(Syracuse)[2,2], labels="b)", cex=0.8)
plot(Syracuse, border="grey60")
plot(Sy13_nb, coords, add=TRUE, pch=".")
text(bbox(Syracuse)[1,1], bbox(Syracuse)[2,2], labels="c)", cex=0.8)
par(oopar)
<<zfig>>
<<figreset>>
@ 
\caption{Distance-based
neighbours: frequencies of numbers of neighbours by census tract}
\label{fig:NB_dnn_cards}
\end{figure}

Figure~\ref{fig:NB_dnn} shows how the numbers of distance-based
neighbours increase with moderate increases in distance. Moving
from $0.75$ times the minimum all-included distance, to the
all-included distance, and $1.5$ times the minimum \hbox{all-included}
distance, the numbers of links grow rapidly. This is a major
problem when some of the first nearest neighbour distances in a
study area are much larger than others, since to avoid
no-neighbour areal entities, the distance criterion will need to
be set such that many areas have many neighbours.
Figure~\ref{fig:NB_dnn_cards} shows the counts of sizes of sets
of neighbours for the three different distance limits. In
Syracuse, the census tracts are of similar areas, but were we to
try to use the distance-based neighbour criterion on the
eight-county study area, the smallest distance securing at least
one neighbour for every areal entity is over 38\,km.


\begin{footnotesize}
<<echo=TRUE>>=
dsts0 <- unlist(nbdists(NY_nb, coordinates(NY8)))
summary(dsts0)
@
\end{footnotesize}

If the areal entities are approximately regularly spaced, using 
distance-based neighbours is not necessarily a problem. Provided 
that care is taken
to handle the side effects of ``weighting'' areas out of the
analysis, using lists of neighbours with no-neighbour areas is
not necessarily a problem either, but certainly ought to raise questions. 
Different disciplines handle the definition of neighbours in
their own ways by convention; in particular, it seems that ecologists
frequently use distance bands. If many distance bands are used, they
approach the variogram, although the underlying understanding of spatial
autocorrelation seems to be by contagion rather than continuous.


\section{Higher-Order Neighbours}

Distance bands can be generated by using a sequence of \code{d1} and
\code{d2} argument values for the \code{dnearneigh} function if needed to
construct a spatial autocorrelogram as understood in ecology. In other
conventions, correlograms are constructed by taking an input list of
neighbours as the first-order sets, and stepping out across the graph
to second-, third-, and higher-order neighbours based on the number of
links traversed, but not permitting cycles, which could risk making $i$ a
neighbour of $i$ itself \citep[][p. 203]{osullivan+unwin:03}. The
\code{nblag} function takes an existing neighbour list
and returns a list of lists, from first to \code{maxlag} order neighbours.


\begin{footnotesize}
<<echo=TRUE>>=
Sy0_nb_lags <- nblag(Sy0_nb, maxlag=9)
@
\end{footnotesize}

y
\enlargethispage*{1pc}

\begin{table}[!b]
\tabcolsep5pt \vspace*{-6pt} \centering \caption{Higher-order
contiguities: frequencies of numbers of neighbours by order of
neighbour list} \label{tab:nblag}
\begin{footnotesize}\vspace*{-6pt}
  \addvspace{5pt}
<<results=tex,echo=FALSE>>= 
library(xtable)
names(Sy0_nb_lags) <- c("first", "second", "third", "fourth", "fifth", "sixth", "seventh", "eighth", "ninth")
res <- sapply(Sy0_nb_lags, function(x) table(card(x)))
mx <- max(unlist(sapply(Sy0_nb_lags, function(x) card(x))))
nn <- length(Sy0_nb_lags)
res1 <- matrix(0, ncol=(mx+1), nrow=nn)
rownames(res1) <- names(res)
colnames(res1) <- as.character(0:mx)
for (i in 1:nn) res1[i, names(res[[i]])] <- res[[i]]
print(xtable(t(res1), align=c("r", "|", rep("r", nn)), digits=0), floating=FALSE)
@
\end{footnotesize}
\end{table}


{\spaceskip3pt plus2pt minus2pt Table~\ref{tab:nblag} shows how the wave of connectedness in the
graph spreads to the third order, receding to the eighth order,
and dying away at the ninth\break order -- there are no tracts nine
steps from each other in this graph. Both the distance bands and
the graph step order approaches to spreading neighbour\-hoods can
be used to examine the shape of relationship intensities in
space, like the variogram, and can be used in attempting to look
at the effects of scale.}

\section{Grid Neighbours}

When the data are known to be arranged in a regular, rectangular
grid, the \code{cell2nb} function can be used to construct
neighbour lists, including those on a torus. These are useful for
simulations, because, since all areal entities have equal numbers
of neighbours, and there are no edges, the structure of the graph
is as neutral as can be achieved. Neighbours can either be of
type rook or queen.


\begin{footnotesize}
<<echo=TRUE>>=
cell2nb(7, 7, type="rook", torus=TRUE)
cell2nb(7, 7, type="rook", torus=FALSE)
@
\end{footnotesize}

When a regular, rectangular grid is not complete, then we can use
knowledge of the cell size stored in the grid topology to create
an appropriate list of neighbours, using a tightly bounded
distance criterion. Neighbour lists of this kind are commonly
found in ecological assays, such as studies of species richness
at a national or continental scale. It is also in these settings,
with moderately large $n$, here $n=3$,103, that the use of a
sparse, list based representation shows its strength. Handling a
$281 \times 281$ matrix for the eight-county census tracts is
feasible, easy for a $63 \times 63$ matrix for Syracuse census
tracts, but demanding for a 3,$103 \times 3$,103 matrix.

\begin{footnotesize}
<<echo=TRUE>>= 
data(meuse.grid)
coordinates(meuse.grid) <- c("x", "y")
gridded(meuse.grid) <- TRUE
dst <- max(slot(slot(meuse.grid, "grid"), "cellsize"))
mg_nb <- dnearneigh(coordinates(meuse.grid), 0, dst)
mg_nb
table(card(mg_nb))
@
\end{footnotesize}


\begin{thebibliography}{}

\bibitem[Avis and Horton, 1985]{avis+horton:1985}
Avis, D. and Horton, J. (1985).
 Remarks on the sphere of influence graph.
 In Goodman, J.~E., editor, {\em Discrete Geometry and Convexity}.
  New York Academy of Sciences, New York, pp 323--327.

\bibitem[Matula and Sokal, 1980]{matula+sokal:80}
Matula, D.~W. and Sokal, R.~R. (1980).
 Properties of {G}abriel graphs relevant to geographic variation
  research and the clustering of points in the plane.
 {\em Geographic Analysis}, 12:205--222.

\bibitem[O'Sullivan and Unwin, 2003]{osullivan+unwin:03}
O'Sullivan, D. and Unwin, D.~J. (2003).
 {\em Geographical Information Analysis}.
 Wiley, Hoboken, NJ.

\bibitem[Toussaint, 1980]{toussaint:80}
Toussaint, G.~T. (1980).
 The relative neighborhood graph of a finite planar set.
 {\em Pattern Recognition}, 12:261--268.

\bibitem[Waller and Gotway, 2004]{WallerGotway:2004}
Waller, L.~A. and Gotway, C.~A. (2004).
\newblock {\em Applied Spatial Statistics for Public Health Data}.
\newblock John Wiley \& Sons, Hoboken, NJ.

\end{thebibliography}

\end{document}