Uniform-grid spatial bin index¶
A flat regular-grid index that retrieves local spatial candidates for exact relation or distance checks.
Core Idea¶
A uniform-grid spatial bin index divides a spatial domain into regular cells, records which items belong in each cell, and retrieves nearby candidates by visiting relevant cells. It narrows the pairs that need a later exact intersection or distance check. Sharing a bin does not itself prove that two items intersect or are within a requested distance.[ref-00d577165eb8][ref-7953fa898db8]
Scope of Application¶
Franklin describes flat-grid bins for geometric element intersection candidates. LAMMPS uses regular neighbor bins and a stencil of nearby cells to assemble atom neighbor lists. The spatial coordinates, cell membership, and local search transfer between the cases; their enrollment and exact predicates differ.[ref-00d577165eb8][ref-7953fa898db8]
Clarity¶
State the cell size, which cell owns a coordinate on a grid line, how items are enrolled, which cells a query visits, and which predicate confirms a result. Giving each location one owning cell is an analytic implementation convention for addressing boundaries, while an extended item such as a segment may intersect several cells. Cell size affects how many bins and candidate items are visited in the inspected methods.[ref-00d577165eb8][ref-7953fa898db8]
Manages Complexity¶
The grid filters potential matches by location before applying an exact test. It can reduce comparisons when local cells contain few relevant objects. A poor width or crowded cells can make it inefficient, so the index promises neither a universal speedup nor a final answer from bin membership alone.[ref-00d577165eb8][ref-7953fa898db8]
Abstract Reasoning¶
Separate coverage from cost. Every true match must appear in a visited cell or stencil; then occupancy and cell visits determine how many false candidates remain. Removing the grid while keeping the exact test changes candidate-generation cost, not the correct final answer. Removing the exact test turns confirmed matches into possible matches.[ref-00d577165eb8][ref-7953fa898db8]
Knowledge Transfer¶
The location-partition and candidate-retrieval roles transfer from segments to atoms. Segment references may occupy multiple cells; an atom in the inspected LAMMPS build occupies one bin and searches neighboring bins. The catalog's Partition Prime is inside the spatial grid because coordinate locations are divided into one owning cell each; items need not be partitioned that way.
Example¶
Franklin's uniform grid puts geometric elements into the cells they traverse and compares pairs sharing a cell before testing intersection. LAMMPS puts each atom into a neighbor bin, visits a nearby-bin stencil, and tests candidate distances against a neighbor-list cutoff. In both cases the regular cells generate candidates and the downstream predicate decides which qualify.[ref-00d577165eb8][ref-7953fa898db8]
Relationships to Other Abstractions¶
Current abstraction Uniform-grid spatial bin index Domain-specific
Parents (1) — more general patterns this builds on
-
Uniform-grid spatial bin index is part of Partition Prime
The grid's mutually exclusive, collectively exhaustive coordinate cells are an internal partition that makes cell addressing and local retrieval possible.
Hierarchy path (1) — routes to 1 parentless root
- Uniform-grid spatial bin index → Partition → Set and Membership
Neighborhood in Abstraction Space¶
Uniform-grid spatial bin index sits in a sparse region of the domain-specific corpus (94th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2721 abstractions)
Nearest neighbors
- Polyhedral Complex — 0.78
- De Bruijn Torus — 0.78
- Finite subdivision rule — 0.78
- Sphere packing — 0.78
- Trilinear Interpolation — 0.77
Computed from structural-signature embeddings · 2026-10-17
Not to Be Confused With¶
Histogram bins count values in ranges; these bins retain spatial item references for local candidate retrieval. A quadtree uses recursive subdivisions rather than a flat regular grid. The inspected grid sources describe candidate generation and warn or illustrate how width and crowding affect cost.[ref-00d577165eb8][ref-7953fa898db8] The live Spatial Indexing Prime has a stronger typical output-sensitive cost signature, which a correct but crowded grid does not guarantee. These are different identity tests, even though all concern position-aware retrieval.
References¶
[^ref-00d577165eb8]: W. Randolph Franklin, “Geometry Applications,” §5, “Uniform Grids”, first-person author account, directly inspected. It describes flat-grid traversal and co-cell pair comparison, with workload-dependent performance. The linked 1989 original paper was identified but its PDF body was not directly opened for this draft; no unverified grid-parameter rule is attributed to it. [^ref-7953fa898db8]: LAMMPS project, Developer Guide 30Sep2026, §4.4.3, “Neighbor lists”, official release documentation whose displayed git info was 30Sep2026 when inspected; especially paragraphs on neighbor cutoff and rebuilding, regular bins and stencils, atom enrollment, exact distance check, and bin-size tradeoff. The live documentation URL may later advance.