1 Diagonal adjacency in grid graphs
Diagonal adjacency describes a “neighbor” relation on a regular grid where two cells (or vertices) are treated as adjacent when they touch at a corner, rather than sharing a full edge. This notion is used to define local interaction rules, connectivity, and permissible movements on discrete spatial structures.
1.1 Basic definition of neighbor relations
Consider a 2D grid of square cells with integer coordinates. Under diagonal adjacency, a cell is considered adjacent to another cell if their positions differ by one step in both coordinate directions (e.g., from \((i,j)\) to \((i\pm1, j\pm1)\)). In a vertex-based view, this corresponds to corner-to-corner contact in the induced cell arrangement or, equivalently, allowing moves that change both coordinates simultaneously.
1.2 Corner-touching versus edge-sharing
The distinction central to the term is whether adjacency requires shared area/edge or allows only corner contact. Edge-sharing adjacency (sometimes called side adjacency) treats two cells as neighbors only when they share a common side. Corner-touching adjacency extends the neighbor set to include diagonal cells that meet only at a point. When combined, these rules alter the graph’s local structure and global connectivity.
1.3 Relation to 2D lattice structure
Diagonal adjacency arises naturally from the geometry of the square lattice, where each cell has diagonal neighbors aligned with the lattice’s four diagonal directions.
1.3.1 Adjacency on square cells
For a square-cell tiling, each cell has up to eight neighbors if both side and corner adjacency are permitted. If only diagonal adjacency is used by itself, the neighbor count is smaller and depends on whether boundary conditions are considered. The classification of “neighbor directions” matches the eight compass directions: north, south, east, west, and the four diagonals.
1.3.2 Adjacency on rectangular grids
On a rectangular grid (still aligned with orthogonal axes), the same relative rule applies: a diagonal neighbor is reached by moving one unit along each axis. The difference between square and rectangular settings is mainly in scaling and indexing ranges, not in the combinatorial pattern of corner contact. The neighbor relation remains translation-invariant for interior cells, with boundary truncation near the edges.
2 Neighbor models: 4-neighborhood vs 8-neighborhood
In grid-based modeling, two standard adjacency models are frequently contrasted. The choice between them affects how paths, regions, and connectivity are defined.
2.1 4-neighborhood (side adjacency) baseline
The 4-neighborhood model includes only side-sharing neighbors: from \((i,j)\), neighbors are \((i\pm1,j)\) and \((i,j\pm1)\). This model treats diagonal cells as non-neighbors, preventing corner-only contact from creating connectivity.
2.2 8-neighborhood (includes diagonal adjacency)
The 8-neighborhood model augments side adjacency with corner-touching neighbors: it adds \((i\pm1, j\pm1)\). Under this rule, diagonal steps are allowed, and corner-touching regions can merge in the connectivity graph.
2.3 Implications for connectivity
Because adjacency defines graph edges, changing from 4- to 8-neighborhood changes which cells can reach one another through successive local steps.
2.3.1 Paths and reachability
Allowing diagonal adjacency typically reduces the number of steps needed to travel between two points that are offset in both coordinates. Reachability can also expand: configurations that are disconnected under 4-neighborhood may become connected once corner-to-corner contact is permitted.
2.3.2 Connected components under different rules
Connected components are sets of cells linked through adjacency edges. Under 8-neighborhood, cells separated only by corner gaps may belong to the same component, while 4-neighborhood would split them into different components. This difference is especially important in segmentation tasks, where “touching at a point” may or may not be intended as continuity.
3 Graph-theoretic formulation
Diagonal adjacency can be formalized by converting grid cells or lattice points into a graph, where adjacency corresponds to graph edges.
3.1 Representing grids as graphs
A grid graph can be defined by choosing its vertices (cells or points) and then adding edges between vertices that satisfy the chosen neighbor relation. In the cell-based model, a vertex represents a cell coordinate; in the point-based model, a vertex represents a lattice point, and corner contact can be interpreted via the induced cell adjacency.
3.2 Adjacency matrices and graph edges
With a fixed ordering of vertices, the neighbor relation can be encoded in an adjacency matrix \(A\). For two vertices \(u\) and \(v\), \(A_{uv}=1\) indicates that \(u\) and \(v\) are diagonal neighbors (or neighbors under a broader rule that includes them). Under an undirected model, \(A\) is symmetric.
3.3 Degree of vertices under diagonal adjacency
The degree of a vertex equals the number of neighbors it has under the defined adjacency rule. Diagonal adjacency changes degrees relative to purely side-based models.
3.3.1 Boundary and interior vertex degrees
For an interior cell on a sufficiently large 2D grid:
- Under 4-neighborhood, the degree is 4.
- Under 8-neighborhood, the degree is 8.
Near boundaries, degrees drop because some potential neighbors lie outside the grid. The pattern of degree reduction depends on whether the implementation treats outside cells as nonexistent (common) or uses wrap-around boundary conditions (less common).
3.3.2 Symmetry and undirected edge modeling
When the adjacency rule depends only on relative offsets and not on direction, edges can be modeled as undirected. This yields symmetrical connectivity: if cell \(u\) is adjacent to \(v\), then \(v\) is adjacent to \(u\). Asymmetry can arise only if the rule is directional or weighted in a non-symmetric way.
4 Higher-dimensional diagonal adjacency
The idea extends beyond 2D grids by classifying adjacency according to which coordinates differ by one unit.
4.1 3D face, edge, and corner adjacency
In three dimensions, a cubic lattice introduces multiple “touching” types:
- Face adjacency: cells share a face (one coordinate differs, two are equal).
- Edge adjacency: cells touch along an edge (two coordinates differ by one, one is equal).
- Corner adjacency: cells meet only at a corner (all three coordinates differ by one).
Diagonal adjacency in 3D is often associated with allowing edge and corner contacts, depending on the model’s intention, rather than only corner contacts.
4.2 Generalization to n-dimensional hypercubes
On an \(n\)-dimensional grid, one can define neighbors by restricting how many coordinate components are allowed to change. Corner-to-corner corresponds to simultaneously changing all \(n\) coordinate components by \(\pm1\). More generally, “diagonal-like” movement can be modeled by allowing changes in any subset of coordinates.
4.3 Counting neighbors in d dimensions
Neighbor counts follow from combinatorics: each coordinate can change by either \(+1\) or \(-1\) when that coordinate is allowed to differ.
4.3.1 Corner-to-corner adjacency counts
If “corner-to-corner” means all \(d\) coordinates change by \(\pm1\), then each coordinate has two sign choices. This yields \(2^d\) corner neighbors for an interior vertex. As with 2D, boundary truncation reduces counts near the edges unless wrap-around or toroidal boundaries are assumed.
5 Algorithmic relevance
Adjacency choices directly shape the behavior of common algorithms that operate on grids.
5.1 Grid traversal and shortest paths
When diagonal adjacency is permitted, shortest-path computations on unweighted grids change because diagonal steps increase the set of edges available. In such settings, breadth-first search can find the minimum number of moves under the given adjacency model, which corresponds to different metrics (see later distance interpretations).
5.2 Flood fill and region labeling
Flood fill treats adjacency as a rule for how regions grow. With 4-neighborhood, growth cannot pass through a point-only touch; with 8-neighborhood, point contacts can connect regions. This affects boundary smoothness, perceived connectivity, and the granularity of detected areas.
5.3 Border detection and connectivity constraints
Border and contour detection often depends on whether adjacency across corners is considered continuity. A region that is separated by a one-cell diagonal gap under 4-neighborhood may merge under 8-neighborhood, changing the set of border cells. This is particularly relevant when enforcing “connectivity constraints” to prevent unintended merges.
5.3.1 Effects on diagonally touching regions
Diagonally touching regions are a key failure mode in models that use corner adjacency unintentionally. If a process intends separate objects, allowing diagonal adjacency can merge them at a single pixel/cell contact, producing topological differences such as fewer connected components and altered shapes.
6 Distance and metric interpretations
Diagonal adjacency aligns naturally with distance measures used to interpret movement on grids.
6.1 Chebyshev distance and diagonal movement
When moves allow changing both coordinates simultaneously (as in 8-neighborhood on a 2D grid), the number of steps to reach a target often corresponds to the Chebyshev distance: the maximum of the coordinate differences. This reflects that a diagonal step can “reduce” both coordinate gaps at once.
6.2 Manhattan distance and side-only movement
Under side-only movement (4-neighborhood), reaching \((x,y)\) from \((x_0,y_0)\) typically requires a number of steps equal to the Manhattan distance: the sum of absolute coordinate differences. Each step can change only one coordinate, so progress in one direction comes at the cost of additional steps in the other.
6.3 Relating path length to metric choice
The adjacency model and the metric are coupled: the combinatorial shortest path length under an unweighted graph corresponds to a particular grid metric. Selecting diagonal adjacency therefore implicitly selects a notion of distance that matches the allowed movement directions.
7 Common implementations and conventions
In practice, diagonal adjacency is implemented through coordinate rules, careful indexing, and efficient neighbor enumeration.
7.1 Coordinate-based adjacency rules
In code, a cell at \((i,j)\) can generate neighbor offsets:
- 4-neighborhood offsets: \((\pm1,0)\), \((0,\pm1)\)
- 8-neighborhood offsets: plus \((\pm1,\pm1)\)
For higher dimensions, the same logic extends by generating sign combinations over the coordinates allowed to change.
7.2 Indexing conventions and boundary handling
Implementations must decide how to treat neighbors beyond the grid:
- Exclude out-of-bounds cells (common in finite arrays).
- Clamp to boundaries (less standard for graph adjacency).
- Use wrap-around indices (toroidal grids), which preserve uniform degrees.
These choices influence connectivity, especially for algorithms that rely on repeated local expansions.
7.3 Efficient neighbor generation in code
Efficiency matters in large grids. Common approaches include:
- Precomputing neighbor offset lists for each adjacency type.
- Using loops over a small fixed set of offsets.
- Avoiding repeated bounds checks when possible by iterating interior cells separately from boundary cells.
Such patterns keep runtime predictable since the number of neighbors per cell is bounded.
8 Variants and edge cases
Diagonal adjacency can lead to subtle behaviors in complex configurations, particularly when geometry or obstacles create narrow connections.
8.1 Diagonal adjacency in the presence of obstacles
With obstacles, diagonal moves may allow paths that “pass through” corners of blocked regions. Depending on the application, this can be desirable (allowing traversal around a corner) or undesirable (treating corner contact as unrealistic physical connectivity). Some systems refine the rule by also requiring that certain adjacent side cells are free, preventing corner-cutting.
8.2 Ambiguous cases with “thin” connections
In raster data, objects may touch only at a narrow diagonal bridge (one cell wide). Under 8-neighborhood, such a bridge can create continuity that visually seems implausible. Under 4-neighborhood, it can break connectivity entirely. This ambiguity motivates careful choice of adjacency and sometimes additional morphological checks.
8.3 Consistency requirements for equivalence relations
Neighbor-based connectivity should align with the intended equivalence relation: typically, “connected” means reachable via repeated adjacency steps. However, mixing different adjacency models for foreground and background can create contradictory interpretations, especially in image processing. Consistency often requires a coherent selection of connectivity rules across the modeled entities.
9 Applications
Diagonal adjacency appears across multiple domains where discrete grids represent space or states.
9.1 Image processing and pixel connectivity
In binary image analysis, connectivity determines which foreground pixels belong to the same object. Using 4-neighborhood or 8-neighborhood changes the outcome of component labeling, hole detection, and contour extraction. The diagonal adjacency rule thus influences both quantitative counts (number of components) and qualitative shape descriptions.
9.2 Cellular automata and lattice dynamics
Some cellular automata define neighborhoods that include diagonals to model more isotropic local interactions. Allowing diagonal adjacency can produce smoother, more symmetric propagation patterns, while excluding it yields more axis-aligned dynamics. The neighbor model therefore affects qualitative behavior of the automaton.
9.3 Spatial indexing on discrete grids
In spatial indexing structures for grid-based environments (e.g., occupancy maps or discrete sampling), adjacency determines which cells are considered adjacent states. This affects search efficiency, path feasibility, and the granularity of local planning. Diagonal adjacency can improve navigability in coarse representations by permitting diagonal transitions that better match continuous motion assumptions.