--- # **F5 EXTENSION SPECIFICATION PART 2: Neighborhood Representations and Combinatorial Maps** ### Status: Tentative Proposal --- # 0. Introduction and Scope This document is Part 2 of the F5 extension specification series. It is a **tentative proposal** — the constructs described here are theoretically derived from the established F5 model and are internally consistent with the core specification (F5Layout.md) and Part 1 (F5_Extension_1_NamedTypes.md), but **none of this has been implemented**. It is offered as a worked-out design proposal to guide future implementation, not as a description of existing behaviour. This document introduces: - **Neighborhood Representations** (§3): self-referential Representations expressing adjacency information, which are already structurally valid under the core spec and require no new mechanism - **Combinatorial map dart Fields** (§4): an optional layer above the connectivity types defined in Part 1, expressing half-edge and n-map permutation structure as sibling Fields with normative attributes on the ChartDomain's committed types This document depends on Part 1 (F5_Extension_1_NamedTypes.md) for: - ChartDomain and chart object structure (Part 1 §3) - Connectivity type member naming conventions: the simplex scheme {ii, ij, jj} (Part 1 §5.4) - The `ChartDomain` attribute on committed types (Part 1 §6.3) This extension is strictly additive. No core spec rules are modified. **Conformance levels:** - **Layer 0** — Connectivity ChartDomains and simplex naming (defined in Part 1): the foundation. No dart semantics. May be used independently. - **Layer 1** — Neighborhood Representations (§3): self-referential Representations. Valid under the core spec; clarified and documented here. - **Layer 2** — Combinatorial map dart Fields (§4): proposed extension, not yet implemented. Requires Layer 0. A validator implementing only Layer 0 and Layer 1 MUST correctly ignore the dart attributes and Fields described in Layer 2. --- # 1. Background ## 1.1 Combinatorial maps Combinatorial maps (Edmonds 1960, extended by Lienhardt to n-dimensional quasi-manifolds) represent topological structures via a set of **darts** D and **permutation operations** (involutions α_i and permutation σ) encoding adjacency between oriented incidence elements. The half-edge (2D) and half-face (3D) data structures are specialisations. In F5, darts are not modeled as a new Skeleton type — they would be structurally indistinguishable from vertex Skeletons (both are IndexDepth=0), which defeats the identity-based semantics of the core spec. Instead, the **entry space of an existing Positions field** within a relative Representation serves as the dart enumeration. Each row of the Positions array is one dart. Permutation operations are stored as sibling Fields in the same Representation group. This design keeps the simple triangle mesh case simple: a user who only needs connectivity uses only the Layer 0 types defined in Part 1, without any dart structure. The dart layer is purely additive. ## 1.2 Relationship to the simplex naming scheme Part 1 §5.4 defines the simplex naming scheme: triangle connectivity is stored as `struct { int32 ii, ij, jj }` under the `triangular` ChartDomain. This document builds directly on that: the three entries of each triangle row — `ii`, `ij`, `jj` — are the three darts of that triangle. The dart index space has 3 × N_triangles entries. The naming convention of the member names directly maps to the dart structure: `ii` is the dart at the first barycentric position, `ij` at the second, `jj` at the third. --- # 2. The `combinatorial` ChartDomain The permutation Fields of a combinatorial map are integer arrays indexing into the dart entry space. They use a dedicated ChartDomain to signal their nature to readers: ``` /Charts/combinatorial/ SinglePrecision/ Point <- int32 scalar Attribute ChartDomain: "combinatorial" Attribute F5::DartSource: (present; value advisory) DoublePrecision/ Point <- int64 scalar (for meshes with > 2^31 darts) Point <- soft link -> SinglePrecision/Point ``` The `F5::DartSource` attribute on the committed `combinatorial/Point` type is a **presence signal**: its existence on the type (not its value) marks any Field using this type as a dart permutation Field. At read time, the source Positions field is identified as the sibling Field in the same Representation group whose committed type carries `F5::DartPermutations`. This design avoids storing file-specific paths or object references in a globally shared committed type. --- # 3. Neighborhood Representations (Layer 1) ## 3.1 Definition and motivation Neighborhood information — which vertices are adjacent to a given vertex, which cells share a face — is an intrinsic topological property of a Skeleton. It belongs neither in a coordinate Representation (it is not geometry) nor in a relative Representation pointing to a different Skeleton (it is not a cross-topology relation). The correct location is a **self-referential Representation**: a Representation subgroup of a Skeleton whose name matches the Skeleton's own name. Per core spec §6, a subgroup of a Skeleton is a Representation if its name matches either a Chart name (coordinate) or another Skeleton name (relative). The Skeleton's own name is structurally valid as the target. This requires no new mechanism. ## 3.2 Structure ``` Vertices/ Vertices/ <- self-referential relative Representation Positions <- integer array; each row lists neighbor vertex indices ``` `Vertices/Vertices/Positions` expresses: for each vertex, the set of neighboring vertices. The Positions field indexes into the Vertices Skeleton's own index space. For **fixed-valence** neighborhoods (e.g. all vertices have exactly 6 neighbors on a regular grid), Positions uses a named simplex-like type — a struct with a fixed number of integer members. For **variable-valence** neighborhoods (general unstructured meshes), the field is fragmented (core spec §8.2) with one fragment per vertex, or uses a separated compound with an offset array. ## 3.3 Applicability to all Skeletons Self-referential Representations are valid for any Skeleton: ``` Faces/ Faces/ <- face-face adjacency (shared edge) Positions <- type: struct { int32 ii, ij, jj } (3 face neighbors) using the triangular simplex naming from Part 1 §5.4 Cells/ Cells/ <- cell-cell adjacency Positions <- neighbor cell indices (type depends on cell valence) ``` ## 3.4 Reader requirement Readers that encounter a self-referential Representation MUST NOT treat it as an error. It is structurally valid per core spec §6. Readers that do not implement neighborhood queries MAY ignore these Representations. --- # 4. Combinatorial Map Dart Fields (Layer 2 — Tentative Proposal) ## 4.1 Dart attributes on the connectivity ChartDomain type Two attributes are placed on the committed `Point` type of the connectivity ChartDomain (e.g. `/Charts/triangular/SinglePrecision/Point`) to declare that the entry space of any Positions field using this type constitutes a dart enumeration: ### F5::DartPermutations - **Placement**: attribute on the connectivity ChartDomain's committed type - **Type**: variable-length HDF5 string array - **Value**: ordered list `[α₀, α₁, ..., α_{n-1}, σ]` giving the names of sibling Fields in the same Representation group that carry each permutation operation, where n = `F5::DartDimension` - **Status**: absent = no dart semantics; presence activates Layer 2 Example on `/Charts/triangular/SinglePrecision/Point`: ``` F5::DartPermutations = ["alpha0", "sigma"] ``` ### F5::DartDimension - **Placement**: attribute on the same committed type as `F5::DartPermutations` - **Type**: int scalar - **Value**: n, the dimension of the combinatorial map (2 for surfaces, 3 for volumes) - **Constraint**: MUST be present if `F5::DartPermutations` is present; its absence alongside `F5::DartPermutations` is a fatal validation error ## 4.2 Permutation Field structure Each Field listed in `F5::DartPermutations`: - Is a **sibling of Positions** in the same Representation group - Uses a committed type from the `combinatorial` ChartDomain (§2) - Has total length = arity(Positions_type) × N_elements(Positions) — one integer per dart - Contains the dart index of the image dart under that permutation - SHOULD be precision-matched to the Positions field The involutions α_i satisfy α_i[α_i[d]] = d for all darts d (self-inverse property). The permutation σ encodes the vertex orbit structure. ## 4.3 Entry-space indexing — the only genuinely new semantic concept The core spec defines Fields as indexing into a **Skeleton's index space**. Permutation Fields introduce something new: indexing into the **entry space of another Field** — specifically into the individual integer entries of a Positions array (each row = one dart), not into Skeleton elements. This is the only semantic extension genuinely beyond the core spec. A Field F indexes into the entry space of Field G when: 1. F and G are siblings in the same Representation group 2. F's committed type carries `F5::DartSource` (from the `combinatorial` ChartDomain) 3. The values in F are non-negative integers less than arity(G) × size(G) Entry-space indexing MUST NOT be used outside the combinatorial map context without a further extension document. ## 4.4 Complete structural example: 2-map on a triangle mesh The dart layer adds two attributes to the `triangular/Point` type and two sibling Fields to the Representation. Everything else is unchanged from the Layer 0 layout. ``` /Charts/ triangular/ SinglePrecision/ Point struct { int32 ii, ij, jj } Attribute ChartDomain: "triangular" Attribute F5::DartPermutations: ["alpha0", "sigma"] Attribute F5::DartDimension: 2 DoublePrecision/ Point struct { int64 ii, ij, jj } Point soft link -> SinglePrecision/Point combinatorial/ SinglePrecision/ Point int32 scalar Attribute ChartDomain: "combinatorial" Attribute F5::DartSource: 1 (presence is the signal) DoublePrecision/ Point int64 scalar Point soft link -> SinglePrecision/Point /t=0/MySurface/ Points/ StandardCartesianChart3D/ Positions type: Cartesian3D/SinglePrecision/Point {float x,y,z} per vertex Faces/ Points/ Positions type: triangular/SinglePrecision/Point {int32 ii,ij,jj} per face Dart attributes inherited from committed type alpha0 type: combinatorial/SinglePrecision/Point int32 array, length 3 x N_faces alpha0[dart] = index of twin dart (edge involution α₀) sigma type: combinatorial/SinglePrecision/Point int32 array, length 3 x N_faces sigma[dart] = next dart in vertex orbit (permutation σ) ``` A Layer-0 reader opens Positions, reads the triangle connectivity, ignores unknown attributes on the committed type. A Layer-2 reader finds `F5::DartPermutations` on the type, loads `alpha0` and `sigma`, and has a fully functional half-edge structure. ## 4.5 Half-edge correspondence For an orientable surface mesh this 2-map is the classical half-edge data structure: | Half-edge concept | F5 dart representation | |-------------------|-------------------------------------------------| | Half-edge / dart | Entry i of Positions (one row = one dart) | | `twin(h)` | `alpha0[i]` — the other dart of the same edge | | `next(h)` | `sigma[i]` — next dart in the vertex orbit | | `prev(h)` | `sigma[sigma[i]]` for triangles (derivable) | | Vertex of h | `Positions[i]` — the target vertex index | | Face of h | `floor(i / 3)` for a triangle mesh | `prev` is derivable and need not be stored. If stored for performance, it SHOULD be added to `F5::DartPermutations` after σ. ## 4.6 3-map for tetrahedral meshes For a tetrahedral mesh (Lienhardt's 3-map / half-face structure): ``` /Charts/tetrahedral/ SinglePrecision/ Point struct { int32 iii, iij, ijj, jjj } Attribute ChartDomain: "tetrahedral" Attribute F5::DartPermutations: ["alpha0", "alpha1", "sigma"] Attribute F5::DartDimension: 3 ``` 4 × N_tetrahedra darts. Each dart is one (tet, vertex-slot) pair. The permutations: - `alpha0`: face involution — the dart on the other side of the same face - `alpha1`: edge involution — the next dart around the same edge - `sigma`: vertex permutation — the next dart in the vertex orbit ## 4.7 n-map generalisation For arbitrary dimension n: a Positions field using an (n+1)-simplex type has n+1 members, yielding (n+1) × N_cells darts. `F5::DartDimension = n`. `F5::DartPermutations` lists n involutions and one permutation. The F5 hierarchy places no constraint on IndexDepth, so higher-dimensional combinatorial maps are accommodated without extension. ## 4.8 Mixed-element meshes For mixed-element meshes (triangles and quads, tetrahedra and hexahedra): - The Positions field is fragmented (core spec §8.2), one fragment per element type - Each fragment uses its own named type from its respective connectivity ChartDomain - `F5::DartPermutations` is placed on each connectivity ChartDomain type independently - The dart index space spans all fragments in offset order (core spec §9) - Permutation fields MUST be consistent across fragment boundaries - Readers MUST concatenate fragments in offset order before applying permutation operations --- # 5. Validation Rules (Layer 2) A validator implementing Layer 2 SHOULD check: - **Permutation field existence**: every name listed in `F5::DartPermutations` on a committed type has a corresponding dataset sibling of the Positions field in each Representation using that type - **Length consistency**: each permutation field has exactly arity(Positions_type) × N_elements(Positions) entries - **Index range**: all permutation field values are valid dart indices in [0, total_dart_count) - **Involution consistency**: for each α_i, α_i[α_i[d]] = d for all darts d - **DartDimension presence**: `F5::DartDimension` MUST accompany `F5::DartPermutations`; its absence alongside `F5::DartPermutations` is fatal - **DartSource coherence**: every Field whose committed type carries `F5::DartSource` MUST be listed in the `F5::DartPermutations` of a sibling Positions field in the same Representation group Violations of length consistency or involution consistency are fatal errors for the affected Representation. --- # 6. Interaction with Core Spec Features ## 6.1 Time-dependence Permutation Fields follow the same time-dependence rules as any other Field (core spec §10). A combinatorial map whose topology is time-independent MUST use symbolic links for permutation fields across timeslices. A CFL-governed AMR structure where the fine mesh topology changes every sub-step would use new dataset objects at each timeslice for the affected permutation fields, while coarser levels remain linked. ## 6.2 Fragmented permutation fields Permutation fields MAY be fragmented with the same structure as their Positions field. Fragment offsets are into the dart index space. All fragments of a permutation field MUST be consistent with all fragments of the corresponding Positions field. ## 6.3 Multi-file merging When merging Grids across files (core spec §4.3), dart indices in merged permutation fields MUST be updated to reflect the concatenated dart index space of the merged Positions fragments. --- # 7. Open Implementation Questions The following questions are identified for resolution during implementation: **Validation cost of involution consistency.** Checking α_i[α_i[d]] = d for all darts requires a full pass over the permutation array. For very large meshes this may be prohibitive as a default check. Validators MAY implement this as an optional "deep validation" mode rather than a mandatory per-read check. **`F5::DartPermutations` on DoublePrecision types.** The attributes are placed on the SinglePrecision committed type in the examples. Should the identical attributes be placed on all precision variants of a connectivity ChartDomain, or is it sufficient to place them on the default (soft-linked) type? The current proposal leaves this open; an implementation SHOULD place them on all precision variants for consistency. **ChartDomain for `combinatorial` across files.** When merging files (core spec §4.3), the `combinatorial` ChartDomain MUST be identical across files. A validator SHOULD verify that the `F5::DartSource` signal is present on all merged type instances. **Dart indices after mesh topology changes.** For a time-evolving mesh where the connectivity changes at some timeslice T, the permutation field is a new dataset at T (time-dependent per core spec §10). The dart indices in the new permutation field must be consistent with the new Positions field at the same timeslice, not with the previous one. Writers MUST ensure this consistency; it cannot be automatically enforced. --- # 8. Summary of Proposed New Elements All elements in this section are **tentative proposals**. None are implemented. | Element | Layer | Status | |---------------------------------------|-------|---------------------------| | Self-referential Neighborhood Rep (§3)| 1 | Valid now per core spec | | `combinatorial` ChartDomain (§2) | 2 | Proposed | | `F5::DartPermutations` attribute (§4.1)| 2 | Proposed | | `F5::DartDimension` attribute (§4.1) | 2 | Proposed | | `F5::DartSource` attribute (§2) | 2 | Proposed | | Entry-space indexing concept (§4.3) | 2 | Proposed — only new semantic | No new hierarchy levels are introduced. No core spec rules are modified. The `F5::` attribute prefix is reserved for normative extension attributes (core spec §6, Part 1 §6.3). Application attributes MUST NOT use this prefix. --- # 9. Literature - Edmonds, J.R.: "A combinatorial representation for polyhedral surfaces." Notices of the American Mathematical Society 7 (1960). - Lienhardt, P.: "N-dimensional generalised combinatorial maps and cellular quasi-manifolds." International Journal of Computational Geometry and Applications 4(3), pp. 275–324 (1994). - Mäntylä, M.: *An Introduction to Solid Modeling*. Computer Science Press (1988). — Defines the half-edge data structure. - Kettner, L.: "Using generic programming for designing a data structure for polyhedral surfaces." Computational Geometry 13(1), pp. 65–90 (1999). — CGAL half-edge reference. The fiber-bundle grounding of the F5 model used throughout this document: - Benger, W. (2005): PhD thesis, FU Berlin / ZIB. https://www.fiberbundle.net/papers/TensorFieldViz.pdf - Benger, W. et al. (2009): "Using Geometric Algebra for Navigation in Riemannian and Hard Disc Space." GraVisMa 2009, Plzen, September 2–4, 2009, pp. 80–89. http://gravisma.zcu.cz/GraVisMa-2009/Papers_2009/!_2009_GraVisMa_proceedings-FINAL.pdf --- # **End of Part 2 (Tentative Proposal)** ---