1 Definition and Motivation

Corner adjacency is a neighborhood relation used in grid- and graph-based settings to declare two elements “neighbors” when they meet only at a single corner point (a shared vertex), rather than sharing a line segment (an edge). The choice of what counts as a neighbor is not purely semantic: it directly affects reachability, connectivity, and the behavior of algorithms built on those relations.

1.1 Basic notion of corner touching

In a 2D lattice, each cell (or pixel) typically occupies an axis-aligned square region. Two cells are corner-adjacent when they touch at exactly one point, such as when one cell is diagonally positioned relative to the other and their squares meet at a vertex. Under this relation, the neighborhood relation is weaker than edge adjacency because contact occurs only at a point rather than across a positive-length boundary.

1.2 Corner adjacency vs. edge adjacency

Edge adjacency (often called side adjacency) requires two cells to share a boundary segment of nonzero length. Corner adjacency relaxes this requirement to allow contact at a single point. As a result, corner adjacency increases the number of neighbors each cell can have, and it can connect regions that would otherwise remain separated under a side-only rule.

1.3 Corner adjacency in graphs and grids

Corner adjacency appears in both discrete geometric models and computational graph constructions. In grids, it is used to define neighborhood connectivity for cells, pixels, or lattice points. In graphs, it can be encoded by defining which elements share a “contact” relationship at a vertex, thereby producing different adjacency graphs depending on the modeling choice.

2 Formal Models

Formalizing corner adjacency requires specifying (i) what the elements are (cells, pixels, lattice points), (ii) what geometry they occupy, and (iii) how adjacency edges in the derived graph are created from geometric contact.

2.1 Grid and cell representations

A common model treats a 2D grid as a collection of axis-aligned square cells indexed by integer coordinates. Each cell corresponds to a unit square in the plane, and corner adjacency can be defined by whether two such squares share a vertex.

2.1.1 Adjacency via shared vertices

Let each cell be identified by indices \((i,j)\), representing the square region \([i,i+1]\times[j,j+1]\). Two cells \((i,j)\) and \((i',j')\) are corner-adjacent if their corresponding squares intersect at exactly one point and that point is a common corner of both squares. In the axis-aligned square setting, this typically corresponds to “diagonal” indices where \(i-i'=1\) and \(j-j'=1\), provided no edge overlap occurs.

2.2 Graph-theoretic formulation

A graph-theoretic approach builds an abstract adjacency graph whose structure depends on how adjacency is defined from the underlying grid.

2.2.1 Vertices representing cells or points

One can construct a graph \(G=(V,E)\) where each vertex in \(V\) corresponds to either a cell/pixel or a lattice point, depending on the chosen representation. If vertices represent cells, the adjacency relation connects cell-vertices that are geometrically corner-touching. If vertices represent points, “corner adjacency” may be expressed in terms of whether points connect through a shared grid vertex or through a derived geometric rule.

2.2.2 Edges defined by corner contact

Under a cell-based model, an edge \((u,v)\in E\) exists exactly when the corresponding cells share a corner point. The result is a graph with additional edges relative to an edge-adjacency-only model. This changes graph distances, connectivity components, and the set of feasible paths for traversal algorithms.

2.3 Dimensional extensions

Corner adjacency generalizes beyond 2D grids by interpreting “shared corner” as sharing a lower-dimensional face in higher dimensions.

2.3.1 2D corner adjacency

In 2D, each interior cell can have up to four corner-adjacent cells (the diagonally positioned neighbors). Edge-adjacent neighbors are up to four as well, so switching from side-only to side-plus-corner alters the maximum local degree.

2.3.2 3D corner (vertex) adjacency

In 3D, if cells are axis-aligned cubes, the analogue of “corner adjacency” is contact at a single grid vertex. Cubes that meet only at a point are vertex-adjacent (3D corner-adjacent). For interior cubes in a uniform lattice, the number of such corner neighbors is eight, corresponding to the eight diagonal directions around a cube in the discrete grid.

3 Neighborhood Systems

Corner adjacency is one element in a broader family of neighborhood definitions used in grid algorithms, each producing different notions of connectivity.

3.1 Alternative neighborhood definitions

Neighborhood rules typically arise from including or excluding diagonal relations and from comparing different standard templates.

3.1.1 4-neighborhood (edge) vs 8-neighborhood (including corners)

In 2D image and grid contexts with square pixels, a 4-neighborhood commonly includes the four edge-adjacent pixels (up, down, left, right). An 8-neighborhood extends this to include the four diagonal corner-adjacent pixels as well. Under 8-neighborhood, diagonal touch becomes sufficient to treat two pixels as directly connected.

3.1.2 Moore vs von Neumann neighborhood

The von Neumann neighborhood corresponds to edge adjacency (4-neighborhood in 2D). The Moore neighborhood corresponds to including corners (8-neighborhood in 2D). These names are widely used in discrete systems and cellular automata because they describe neighborhood shapes in a concise way.

3.2 Connectivity implications

Changing the neighborhood definition changes which sets of cells form connected regions, which in turn affects component labeling and topology-like properties in discrete approximations.

3.2.1 Component structure changes

Under edge-only adjacency, diagonally touching regions may be classified as separate components. With corner-adjacency included, those same regions can merge into a single connected component. This can alter counts of components, sizes of components, and the evolution of connected structures across scales.

3.2.2 Boundary effects and “diagonal bridges”

Corner adjacency can create “bridges” that exist only through vertex contact. Such bridges may be considered legitimate connectivity in purely combinatorial models, but they also can introduce artifacts when interpreting the discrete result as an approximation of continuous geometry. Boundaries are where these effects are most pronounced because diagonal contacts occur frequently along object contours in pixelated data.

3.3 Metric interpretations

Neighborhood choices can be interpreted through distance norms that differ in what constitutes a “close” point or cell.

3.3.1 L∞-based adjacency intuition

For lattice points, the Chebyshev distance \(d_{\infty}\) measures closeness by the maximum coordinate difference. Under an \(L_\infty\) intuition in a grid, diagonal points can be seen as equally close as orthogonal ones when both coordinate differences are within a unit step. This aligns with the idea behind including corners in neighborhood systems.

3.3.2 L1-based adjacency intuition

The Manhattan distance \(d_{1}\) counts total coordinate change. Under an \(L_1\) intuition, moving diagonally requires changing both coordinates, which can be treated as “two-step” progress rather than a single adjacency relation. Edge-only neighborhood naturally matches this perspective by treating orthogonal moves as the basic adjacency steps.

4 Applications in Discrete Mathematics and Computing

Corner adjacency is used wherever discrete models must decide how to connect neighboring states, pixels, cells, or discretized geometric elements.

4.1 Lattice path and traversal considerations

Traversal algorithms often rely on adjacency to define which transitions are permitted on a lattice.

4.1.1 Reachability under corner adjacency

Reachability can increase when diagonal corner transitions are allowed. Sets that are disconnected under edge-only moves can become connected if corner-adjacency edges permit alternate routes. This is particularly relevant for modeling motion with limited turn restrictions in grid worlds, or for studying discrete dynamical systems on lattices.

4.1.2 Path length differences

When corners are included, the graph contains additional edges and shortest path lengths (measured in number of adjacency steps) can decrease. The notion of “length” becomes sensitive to the modeling convention: a diagonal corner step may represent a different geometric displacement than an orthogonal step, yet it is still counted as one graph edge in a purely combinatorial formulation.

4.2 Image processing and pixel neighborhood rules

In image analysis, pixel neighborhoods are central to determining connectivity, shapes, and morphological changes.

4.2.1 Connected components with diagonal touch

Connected component labeling depends on whether diagonally adjacent foreground pixels are considered connected. With 8-neighborhood, diagonal contact merges components that are separated only at a corner. With 4-neighborhood, such pixels remain in distinct components. This choice affects quantitative outputs like component counts and region area measurements.

4.2.2 Morphological operations neighborhood choice

Morphological operations such as dilation and erosion can be interpreted through neighborhood structure: dilation expands regions based on which neighbors are reachable. When corner adjacency is included, dilation can “grow” regions diagonally, potentially filling small gaps differently than edge-only dilation. As a result, neighborhood choice influences the shape regularization and noise sensitivity of morphological pipelines.

4.3 Mesh and grid discretization

Discrete topology and computational geometry often depend on adjacency rules to approximate continuous objects.

4.3.1 Influence on discrete topology

When discretizing a surface or volume into grid elements, adjacency determines how the discrete representation encodes connectedness and separation. Corner adjacency can create extra connections between discrete elements that correspond to mere point contact in the underlying continuous model.

4.3.2 Consistency with refinement

As grid resolution increases, the impact of corner-only contacts may diminish or change depending on how objects align with the grid. Consistency under refinement is therefore not guaranteed: a neighborhood definition that is reasonable at one resolution might produce different discrete connectivity behavior at another.

5 Algorithmic Considerations

Algorithms that traverse graphs or compute connectivity must incorporate corner adjacency correctly, including handling coordinate conventions and boundary cases.

5.1 Searching and graph traversal

Graph search procedures operate on the adjacency relation, so the neighborhood choice directly changes their behavior.

5.1.1 BFS/DFS with corner-adjacency edges

Breadth-first search (BFS) and depth-first search (DFS) can be applied unchanged once the adjacency graph is defined. With corner adjacency, each node yields more outgoing neighbor candidates (up to the corresponding corner degree). As a consequence, BFS may explore additional routes earlier, while DFS may follow different branches due to altered adjacency ordering.

5.1.2 Performance and branching factors

Allowing corner adjacency increases branching factor in worst-case grids. This can increase runtime and memory usage, especially for large images or extensive grids. However, graph diameter may decrease due to extra connectivity edges, which can offset some effects in certain tasks that stop early upon reaching a goal.

5.2 Robustness and tie-breaking conventions

Implementation details matter because discrete adjacency often interacts with rounding, degeneracy, and boundary indexing.

5.2.1 Handling degenerate grid cases

On small grids or near boundaries, the number of possible neighbors drops. Correctly enumerating corner-adjacent neighbors requires consistent boundary checks to avoid indexing outside the grid. Degenerate cases can also arise when cells touch only at a conceptual corner due to coordinate quantization; robust adjacency logic helps prevent spurious links.

5.2.2 Coordinate-system dependence

Corner adjacency is defined relative to the grid’s orientation. Under axis-aligned square or cube discretizations, diagonals correspond to corner contacts. If a coordinate transformation changes alignment (for example, rotating a grid representation while still using axis-aligned cells), the correspondence between diagonal moves and geometric corner contact may shift, requiring careful mapping between geometric coordinates and discrete indices.

Corner adjacency is part of a wider landscape of neighborhood relations that extend the basic idea along geometric or combinatorial dimensions.

6.1 k-neighborhood variants on grids

Beyond immediate corner contacts, some systems consider extended neighborhoods with multiple “rings” of adjacency.

6.1.1 Extending beyond immediate corners

A k-neighborhood can include cells within k steps under a specified adjacency rule. If corner adjacency is included at the base level, the expansion effectively allows diagonal movement to propagate outward. This produces neighborhoods that grow more quickly in diagonal directions than edge-only expansions, influencing smoothing, reachability, and local feature extraction.

6.2 Higher-order adjacency

Higher-order adjacency introduces additional constraints beyond simple corner touch, such as requiring alignment or excluding certain contacts.

6.2.1 Corner adjacency with additional geometric constraints

Some models restrict diagonal connectivity based on local configuration, for example by requiring that a corner connection is supported by surrounding cells. These refinements help reduce ambiguous connections where point-only contact may not reflect intended continuous connectivity.

Terminology overlaps across fields, and it is often useful to disambiguate adjacent concepts.

6.3.1 Vertex adjacency vs corner adjacency terminology

“Vertex adjacency” can be used as a synonym for corner adjacency when adjacency is determined by shared vertices. In contrast, “corner adjacency” may more explicitly emphasize the geometric picture of cells touching at corners. Despite occasional differences in emphasis, both terms typically refer to the idea that connectivity is established through a shared point rather than an overlapping side.