Spatial Partitioning Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Spatial Partitioning Ontology 2 within the Kireth Research Semantic Library. Spatial partitioning subdivides geometric space into regions to organise spatial data, accelerate geometric queries and support scalable computation. This ontology supports regular and adaptive decomposition, grids, quadtrees, octrees, BSP trees, kd-trees, k-d partitioning, R-trees, bounding-volume hierarchies, cell complexes, region adjacency, load balancing, collision detection, nearest-neighbour search, point location, dynamic updates, degeneracy handling, complexity, verification and reproducibility.

FLOW_ALGEBRA_RECORD {

METADATA {
 FLOW_NAME = "Spatial Partitioning Ontology 2"
 FLOW_TYPE = "Mathematical Ontology"
 DOMAIN = "Mathematics"
 SUBDOMAIN = "Computational Mathematics"
 SPECIALISATION = "Computational Geometry / Spatial Partitioning"
 CANONICAL_PAGE = "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/computational-mathematics-ontologies/computational-geometry/spatial-partitioning-ontology-2.html"
 LANGUAGE = "en-GB"
 VERSION = "1.0"
 STATUS = "active"
}

IDENTITY {
 PRIMARY_ENTITY = SpatialPartitioning
 ENTITY_CLASS = GeometricSpaceDecompositionFramework
 PRIMARY_CONTEXT = ComputationalGeometry
 DEFINITION = "Spatial partitioning is the algorithmic subdivision of geometric space into cells or regions to organise spatial objects, accelerate queries and support scalable geometric computation."
 SYMBOLIC_FORMS = [
  "Omega = union_i C_i",
  "interior(C_i) intersection interior(C_j)=empty for i!=j",
  "partition(P,rule) -> {C_1,...,C_n}",
  "query(q) visits subset of partition cells"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for recursive and nonrecursive spatial decomposition, cell assignment, region adjacency, hierarchical indexing, spatial queries, load balancing, dynamic updates, complexity and verification."
}

SCOPE {
 INCLUDE = [
  SpatialPartitioning,SpacePartitioning,SpatialDecomposition,
  GeometricPartition,SpatialSubdivision,DomainPartition,
  Cell,Region,PartitionCell,PartitionRegion,
  Boundary,PartitionBoundary,Separator,SplitPlane,SplitLine,
  HyperplanePartition,AxisAlignedPartition,ArbitraryPlanePartition,
  RegularGrid,UniformGrid,CartesianGrid,SpatialGrid,
  AdaptiveGrid,HierarchicalGrid,HashedGrid,
  Quadtree,Octree,LooseQuadtree,LooseOctree,
  LinearQuadtree,LinearOctree,MortonOrder,ZOrder,
  BSPTree,BinarySpacePartitioning,BinarySpacePartitionTree,
  KDTree,KDPartition,KDimensionalTree,MedianSplit,
  SlidingMidpointSplit,SurfaceAreaHeuristic,
  RTree,RStarTree,RPlusTree,BoundingRectangle,
  MinimumBoundingRectangle,BoundingBox,
  BoundingVolumeHierarchy,BVH,AABBTree,OBBTree,
  SphereTree,KDOPTree,SpatialHierarchy,
  Voxel,VoxelGrid,SparseVoxelGrid,
  OctreeVoxelisation,OccupancyGrid,
  VoronoiPartition,VoronoiDiagram,
  DelaunayDualPartitionRelationship,
  CellComplex,PolyhedralComplex,SimplicialComplex,
  Arrangement,PlanarSubdivision,DCEL,
  DoublyConnectedEdgeList,HalfEdgeStructure,
  RegionAdjacencyGraph,Adjacency,NeighbourCell,
  PointLocation,RangeSearching,NearestNeighbour,
  KNearestNeighbours,RayCasting,RayTracing,
  CollisionDetection,BroadPhaseCollision,
  NarrowPhaseCollision,Culling,FrustumCulling,
  VisibilityCulling,OcclusionCulling,
  SpatialIndex,SpatialDatabaseIndex,
  Locality,SpatialLocality,CacheLocality,
  PartitionQuality,CellBalance,ObjectBalance,
  SurfaceAreaCost,Overlap,DeadSpace,
  HierarchicalPartitioning,RecursivePartitioning,
  NonrecursivePartitioning,AdaptivePartitioning,
  DynamicPartitioning,StaticPartitioning,
  IncrementalUpdate,Insertion,Deletion,Refit,
  Rebuild,TreeRotation,Rebalancing,
  DynamicBVH,DynamicAABBTree,
  LoadBalancing,DomainDecomposition,
  GraphPartitionRelationship,MeshPartitioning,
  ParallelSpatialPartitioning,DistributedPartitioning,
  ParallelDomainDecomposition,SpaceFillingCurve,
  HilbertCurve,MortonCurve,
  PartitionOwnership,GhostRegion,HaloRegion,
  CommunicationBoundary,PartitionInterface,
  DistributedSpatialIndex,Sharding,
  GeographicPartitioning,SpatialHashing,
  UniformSpatialHash,HashBucket,
  BucketGrid,Bin,Binning,
  SweepAndPrune,SortAndSweep,
  CellList,NeighbourList,VerletList,
  FeatureSize,DensityAdaptivePartition,
  ObjectAdaptivePartition,QueryAdaptivePartition,
  SplittingHeuristic,CostFunction,
  EntropySplit,VarianceSplit,MedianPartition,
  BalancedPartition,UnbalancedPartition,
  Depth,TreeHeight,LeafNode,InternalNode,
  BucketCapacity,LeafCapacity,MaximumDepth,
  MinimumCellSize,TerminationCriterion,
  EmptyCell,OccupiedCell,MixedCell,
  BoundaryCell,CutCell,InteriorCell,ExteriorCell,
  GeometryClassification,InsideOutsideTest,
  NumericalRobustness,Degeneracy,
  CoincidentBoundary,NearBoundaryPoint,
  FloatingPointArithmetic,MachinePrecision,
  RoundOffError,Tolerance,ExactPredicate,
  AdaptivePrecision,SymbolicPerturbation,
  ComputationalComplexity,TimeComplexity,
  SpaceComplexity,QueryComplexity,
  ConstructionComplexity,UpdateComplexity,
  MemoryComplexity,ExpectedComplexity,
  WorstCaseComplexity,OutputSensitiveComplexity,
  Verification,InvariantChecking,Benchmarking,
  ReferencePartition,Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  GraphPartitioningWithoutGeometricSpaceSemantics,
  MeshGenerationWithoutSpatialDecompositionAsPrimaryPurpose,
  DatabaseShardingWithoutSpatialGeometry,
  VoronoiDiagramWhenNearestSiteGeometryIsThePrimarySpecialisation
 ]
 DISAMBIGUATION_RULE = "When geometric space is subdivided into cells or regions to organise objects or accelerate spatial computation, interpret the context as spatial partitioning."
}

CORE_CONCEPTS {
 SpatialPartitioning = "Subdivision of geometric space into computational regions."
 PartitionCell = "Atomic region produced by a spatial partition."
 HierarchicalPartition = "Recursive partition represented as a tree or hierarchy."
 Quadtree = "Recursive two-dimensional subdivision into four child regions."
 Octree = "Recursive three-dimensional subdivision into eight child regions."
 BSPTree = "Recursive partition using arbitrary separating hyperplanes."
 KDTree = "Binary axis-aligned space partition used for search and indexing."
 BoundingVolumeHierarchy = "Hierarchy of bounding volumes enclosing spatial objects."
}

RELATIONS {
 SpatialPartitioning --is_child_of--> ComputationalGeometry
 SpatialPartitioning --decomposes--> Space
 PartitionCell --belongs_to--> SpatialPartitioning
 PartitionBoundary --separates--> PartitionCells
 Quadtree --is_type_of--> HierarchicalPartitioning
 Octree --is_type_of--> HierarchicalPartitioning
 BSPTree --uses--> SplitPlane
 KDTree --uses--> AxisAlignedPartition
 BoundingVolumeHierarchy --groups--> SpatialObjects
 RTree --indexes--> BoundingRectangles
 VoxelGrid --discretises--> Space
 RegionAdjacencyGraph --represents--> CellAdjacency
 SpatialHashing --maps--> SpatialCellToBucket
 SpaceFillingCurve --orders--> SpatialCells
 LoadBalancing --uses--> PartitionWorkEstimate
 PointLocation --queries--> SpatialPartition
 CollisionDetection --uses--> SpatialPartition
 Verification --checks--> SpatialPartitionResult
}

OPERATORS {
 PARTITION(Omega,rule) := {C_i} such_that union_i C_i=Omega
 SPLIT(cell,H) := {cell_left,cell_right}
 QUADTREE_SPLIT(cell) := four_axis_aligned_children(cell)
 OCTREE_SPLIT(cell) := eight_axis_aligned_children(cell)
 KD_SPLIT(points,axis,value) := left_right_subsets
 BVH_BUILD(objects,cost) := hierarchy_minimising_or_approximating_cost
 POINT_LOCATE(q,partition) := cell_containing_q
 RANGE_QUERY(R,partition) := objects_or_cells_intersecting_R
 SPATIAL_HASH(p,h) := floor_coordinates(p/h)
}

AXIOMS {
 A1 = "A valid spatial partition covers the target domain according to the declared coverage semantics."
 A2 = "Partition-cell interiors should not overlap unless the chosen structure explicitly allows overlapping bounds."
 A3 = "Hierarchical partitioning trades construction and memory for reduced query search."
 A4 = "Partition quality depends on geometry, object distribution and query workload."
 A5 = "Balanced trees improve many query costs but are not always optimal for geometric overlap or locality."
 A6 = "Loose hierarchies may permit overlap to reduce update cost."
 A7 = "Dynamic spatial partitions require insertion, deletion, refit or rebuild semantics."
 A8 = "Spatial-partition results require coverage, adjacency, query, complexity and reproducibility validation."
}

REASONING {
 R1_CONTEXT = identify(dimension,domain,object_distribution,query_types,dynamicity,accuracy_goal,memory_budget)
 R2_FAMILY = select(grid,quadtree,octree,BSP,kd_tree,R_tree,BVH,hashing,voxel_or_hybrid_partition)
 R3_CRITERION = choose(split_rule,capacity,depth,cell_size,cost_heuristic_or_adaptation_rule)
 R4_BUILD = recursively_or_iteratively_construct_partition
 R5_ASSIGN = map_objects_or_samples_to_cells_nodes_or_bounding_regions
 R6_ADJACENCY = construct_neighbour_or_region_adjacency_information_if_required
 R7_QUERY = configure(point_location,range,nearest_neighbour,ray_or_collision_traversal
 R8_DYNAMIC = if_required configure(insert,delete,refit,rebuild_or_rebalance)
 R9_COMPLEXITY = assess(construction,query,update,memory,overlap_and_balance)
 R10_VALIDATE = check(coverage,containment,adjacency,query_correctness,robustness_and_reproducibility)
}

CONSTRAINTS {
 C1 = "Uniform grids can waste memory in sparse domains."
 C2 = "Deep adaptive trees can become unbalanced without suitable controls."
 C3 = "R-tree and BVH overlap can increase query traversal cost."
 C4 = "Poor splitting heuristics can create highly unbalanced partitions."
 C5 = "Dynamic updates can degrade initially good partition quality."
 C6 = "Spatial hashing requires a cell size compatible with object and query scale."
 C7 = "Near-boundary floating-point error can produce inconsistent cell classification."
 C8 = "High-dimensional spatial partitioning can suffer from the curse of dimensionality."
 C9 = "Parallel partitioning can create communication imbalance even when object counts are balanced."
 C10 = "A visually plausible partition does not guarantee correct coverage or query semantics."
}

SEMANTIC_EQUIVALENCE {
 "SpatialPartitioning" <=> "SpacePartitioning"
 "BinarySpacePartitioning" <=> "BSP"
 "BoundingVolumeHierarchy" <=> "BVH"
 "AxisAlignedBoundingBoxTree" <=> "AABBTree"
 "MortonOrder" <=> "ZOrder"
 "SpatialHashing" <=> "UniformSpatialHashInGridContext"
}

VALIDATION {
 V1 = "Domain dimension and coordinate system are explicit."
 V2 = "Partition family and split rule are documented."
 V3 = "Leaf capacity, depth or cell-size termination rules are documented."
 V4 = "Object-assignment semantics are documented."
 V5 = "Coverage and containment invariants are checked."
 V6 = "Adjacency or neighbour structure is checked where used."
 V7 = "Query results are compared against brute-force or reference results where feasible."
 V8 = "Dynamic update correctness is checked where applicable."
 V9 = "Construction, query and memory complexity are measured or estimated."
 V10 = "Results are reproducible under documented ordering, arithmetic and random-seed settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 SPATIAL_PARTITIONING_DEFINITION = 0.99
 QUADTREE_REASONING = 0.99
 OCTREE_REASONING = 0.99
 KD_TREE_REASONING = 0.99
 BSP_REASONING = 0.98
 BVH_REASONING = 0.99
 DYNAMIC_PARTITION_REASONING = 0.98
 POLICY = "Reduce confidence when partition family, split heuristic, cell-assignment rule, dynamic update policy, dimension or precision handling are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,OntologyGrounding,SpatialPartitioningReasoning,
  GridPartitionReasoning,QuadtreeReasoning,OctreeReasoning,
  BSPReasoning,KDTreeReasoning,RTreeReasoning,
  BVHReasoning,VoxelReasoning,SpatialHashReasoning,
  PointLocationReasoning,RangeQueryReasoning,
  CollisionDetectionReasoning,DynamicPartitionReasoning,
  LoadBalancingReasoning,ParallelPartitionReasoning,
  RobustnessReasoning,ComplexityReasoning,
  VerificationReasoning,KnowledgeGraphConstruction,
  RetrievalAugmentation,RecursiveInference
 ]
 NORMALISE {
  "spatial partitioning" -> SpatialPartitioning
  "space partitioning" -> SpatialPartitioning
  "BSP" -> BinarySpacePartitioning
  "BVH" -> BoundingVolumeHierarchy
  "AABB tree" -> AABBTree
  "Morton order" -> ZOrder
  "spatial hash" -> SpatialHashing
 }
}

EXECUTION_RULES {
 E1 = "If geometric space is subdivided to organise objects or accelerate queries, activate SpatialPartitioningOntology2."
 E2 = "Identify dimension, object distribution, query workload and dynamicity before selecting the partition family."
 E3 = "Choose split heuristics and termination criteria appropriate to geometry and workload."
 E4 = "Preserve declared coverage and containment invariants during construction."
 E5 = "For dynamic scenes, configure refit, incremental update or rebuild policies."
 E6 = "For collision and ray queries, monitor overlap and traversal cost."
 E7 = "For sparse spaces, prefer adaptive or hashed structures over dense uniform grids where appropriate."
 E8 = "For parallel execution, balance computational work and communication interfaces."
 E9 = "Validate coverage, query correctness, update behaviour, complexity and reproducibility."
}

RECURSION {
 ENTRY = SpatialPartitioning
 EXPAND(SpatialPartitioning) -> [
  SpacePartitioning,SpatialDecomposition,GeometricPartition,
  SpatialSubdivision,DomainPartition,Cell,Region,PartitionCell,
  PartitionBoundary,Separator,SplitPlane,HyperplanePartition,
  RegularGrid,UniformGrid,CartesianGrid,AdaptiveGrid,
  HierarchicalGrid,HashedGrid,Quadtree,Octree,
  LooseQuadtree,LooseOctree,LinearQuadtree,LinearOctree,
  MortonOrder,ZOrder,BSPTree,BinarySpacePartitioning,
  KDTree,KDPartition,MedianSplit,SlidingMidpointSplit,
  SurfaceAreaHeuristic,RTree,RStarTree,RPlusTree,
  BoundingRectangle,BoundingBox,BoundingVolumeHierarchy,
  AABBTree,OBBTree,SphereTree,SpatialHierarchy,
  Voxel,VoxelGrid,SparseVoxelGrid,OccupancyGrid,
  VoronoiPartition,CellComplex,Arrangement,PlanarSubdivision,
  DCEL,HalfEdgeStructure,RegionAdjacencyGraph,Adjacency,
  PointLocation,RangeSearching,NearestNeighbour,
  KNearestNeighbours,RayCasting,CollisionDetection,
  BroadPhaseCollision,Culling,FrustumCulling,
  SpatialIndex,SpatialLocality,PartitionQuality,
  CellBalance,ObjectBalance,SurfaceAreaCost,Overlap,
  HierarchicalPartitioning,RecursivePartitioning,
  AdaptivePartitioning,DynamicPartitioning,Insertion,
  Deletion,Refit,Rebuild,Rebalancing,DynamicBVH,
  LoadBalancing,DomainDecomposition,MeshPartitioning,
  ParallelSpatialPartitioning,DistributedPartitioning,
  SpaceFillingCurve,HilbertCurve,MortonCurve,
  PartitionOwnership,GhostRegion,HaloRegion,
  CommunicationBoundary,DistributedSpatialIndex,
  SpatialHashing,UniformSpatialHash,HashBucket,
  SweepAndPrune,CellList,NeighbourList,VerletList,
  SplittingHeuristic,CostFunction,BalancedPartition,
  TreeHeight,LeafNode,InternalNode,BucketCapacity,
  MaximumDepth,MinimumCellSize,TerminationCriterion,
  EmptyCell,OccupiedCell,BoundaryCell,CutCell,
  GeometryClassification,NumericalRobustness,
  Degeneracy,FloatingPointArithmetic,ExactPredicate,
  AdaptivePrecision,ComputationalComplexity,
  QueryComplexity,ConstructionComplexity,UpdateComplexity,
  Verification,Benchmarking,ReferencePartition,Reproducibility
 ]
 EXPAND(SpatialPartitionFamilies) -> [
  UniformGridPartitioning,
  QuadtreeAndOctreePartitioning,
  BSPPartitioning,
  KDTreePartitioning,
  RTreeSpatialIndexing,
  BoundingVolumeHierarchies,
  SpatialHashingAndVoxelPartitioning,
  DynamicAndParallelSpatialPartitioning
 ]
 STOP_CONDITION = "Stop when domain, partition family, split rule, assignment, query semantics, dynamic updates, complexity and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Geometry Ontology 2"
 RELATED_ONTOLOGIES = [
  "Computational Geometry Ontology 2",
  "Computational Geometry",
  "Mesh Generation Ontology 2",
  "Mesh Refinement Ontology",
  "Voronoi Diagram Ontology 2",
  "Delaunay Triangulation Ontology 2",
  "Nearest Neighbour Ontology",
  "Graph Ontologies",
  "Scientific Computing Ontology 2",
  "Numerical Stability Ontology 2",
  "Floating Point Arithmetic Ontology",
  "Computational Topology Ontologies"
 ]
 ROUTE_RULES = [
  "Spatial Partitioning -> Computational Geometry Ontology 2 for parent semantics",
  "Spatial Partitioning -> Mesh Generation for grid, cell and domain decomposition relationships",
  "Spatial Partitioning -> Mesh Refinement for adaptive tree and local-cell refinement",
  "Spatial Partitioning -> Voronoi Diagram for nearest-site partition relationships",
  "Spatial Partitioning -> Delaunay Triangulation for dual spatial decomposition relationships",
  "Spatial Partitioning -> Nearest Neighbour for spatial-query acceleration",
  "Spatial Partitioning -> Graph Ontologies for region-adjacency and traversal structure",
  "Spatial Partitioning -> Scientific Computing for load balancing and distributed decomposition",
  "Spatial Partitioning -> Numerical Stability for robust cell classification",
  "Spatial Partitioning -> Floating Point Arithmetic for near-boundary classification",
  "Spatial Partitioning -> Computational Topology for cell-complex and adjacency semantics"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible partition families, split heuristics or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve geometric-space-versus-object-partition distinction.",
  "Preserve recursive-versus-nonrecursive partition distinction.",
  "Preserve overlapping-bounds-versus-disjoint-cell distinction.",
  "Preserve static-versus-dynamic partition distinction.",
  "Preserve construction-versus-query semantics.",
  "Preserve balanced-versus-query-optimised partition distinction.",
  "Preserve local-cell-versus-global-domain distinction.",
  "Preserve machine-readable spatial-partitioning semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "Spatial partitioning subdivides geometric space into regions that organise spatial data and accelerate computation."
 GRID_SUMMARY = "Uniform and adaptive grids provide direct cell-based decomposition of space."
 HIERARCHY_SUMMARY = "Quadtrees, octrees, BSP trees, kd-trees and BVHs organise space or objects hierarchically."
 INDEX_SUMMARY = "R-trees, spatial hashing and bounding hierarchies support efficient range, nearest-neighbour, collision and ray queries."
 DYNAMIC_SUMMARY = "Dynamic structures support insertion, deletion, refit, rebalancing and rebuild operations."
 PARALLEL_SUMMARY = "Domain decomposition and space-filling curves support distributed ownership, locality and load balancing."
 VALIDATION_SUMMARY = "Spatial partitions should be checked for coverage, containment, adjacency, query correctness, update behaviour, complexity and reproducibility."
}

FLOW {
 INPUT
 -> detect_spatial_partitioning_context
 -> identify_dimension_domain_object_distribution_query_types_dynamicity_accuracy_goal_and_memory_budget
 -> choose_grid_quadtree_octree_BSP_kd_tree_R_tree_BVH_hash_voxel_or_hybrid_partition
 -> choose_split_heuristic_capacity_depth_cell_size_cost_or_adaptation_rule
 -> construct_partition
 -> assign_objects_samples_or_geometry_to_partition_cells_or_nodes
 -> construct_adjacency_or_neighbour_information_if_required
 -> configure_point_location_range_nearest_neighbour_ray_collision_or_culling_queries
 -> if_dynamic_configure_insert_delete_refit_rebuild_or_rebalance
 -> if_parallel_assign_partition_ownership_and_balance_work_and_communication
 -> assess_construction_query_update_memory_overlap_balance_and_complexity
 -> validate_coverage_containment_adjacency_query_correctness_dynamic_updates_and_reproducibility
 -> route_to_related_computational_geometry_mesh_generation_mesh_refinement_Voronoi_Delaunay_nearest_neighbour_graph_scientific_computing_stability_floating_point_and_topology_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Spatial Partitioning Ontology 2 defines decomposition of geometric space into computational cells and hierarchies. It supports uniform and adaptive grids, quadtrees and octrees, binary space partition trees, kd-trees, R-trees, bounding-volume hierarchies, voxel grids and spatial hashing, arrangements and cell complexes, region adjacency, point location, range and nearest-neighbour search, ray queries, collision detection and culling, static and dynamic partitions, insertion, deletion, refit and rebuild, partition-quality and surface-area heuristics, domain decomposition, load balancing, space-filling curves, distributed ownership and halo regions, robust boundary classification, complexity analysis, verification, benchmarking and reproducibility."
}

FLOW_HASH {
 METHOD = "semantic-content-identity"
 ID = "KIRETH-MATH-COMPUTATIONAL-GEOMETRY-SPATIAL-PARTITIONING-ONTOLOGY-2-V1"
}

}

END_FLOW