Spatial Partitioning Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the mathematical ontology of spatial partitioning within the Kireth Research Semantic Library. Spatial partitioning divides a geometric domain into regions or cells to support efficient search, indexing, collision detection, visibility, point location, range queries, meshing and hierarchical decomposition. This ontology supports regular and adaptive partitions, grids, quadtrees, octrees, k-d trees, BSP trees, spatial hashing, Voronoi subdivisions, bounding-volume hierarchies, cell adjacency, refinement, query routing and relationships with computational geometry, topology and spatial data structures.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = SpatialPartitioning
 SYMBOLIC_FORMS = [
  "Omega = union_i C_i",
  "C_i intersection C_j = boundary_or_empty",
  "hierarchical spatial decomposition"
 ]
 ENTITY_CLASS = GeometricSubdivisionFramework
 PRIMARY_CONTEXT = ComputationalGeometry
 DEFINITION = "Spatial partitioning is the decomposition of a geometric domain into regions or cells for representation, indexing, querying or computation."
 SEMANTIC_ROLE = "Provides the spatial subdivision framework for search acceleration, point location, range queries, collision detection, visibility, adaptive refinement and hierarchical geometry processing."
}

SCOPE {
 INCLUDE = [
  SpatialPartitioning,
  SpatialSubdivision,
  Cell,
  Region,
  PartitionBoundary,
  Grid,
  UniformGrid,
  AdaptiveGrid,
  Quadtree,
  Octree,
  KDTree,
  BSPTree,
  SpatialHash,
  BoundingVolumeHierarchy,
  VoronoiSubdivision,
  Arrangement,
  PointLocation,
  RangeSearching,
  NearestNeighbour,
  CollisionDetection,
  Visibility,
  HierarchicalPartition,
  AdaptivePartition,
  RecursiveSubdivision,
  CellAdjacency,
  Refinement,
  Coarsening,
  LoadBalancing,
  SpatialIndex
 ]

 EXCLUDE_AS_PRIMARY = [
  PureSetPartitionWithoutGeometricMeaning,
  DatabaseShardingWithoutSpatialStructure,
  MeshOntologyUnlessPartitionCellsFormMeshElements,
  GraphPartitioningWithoutSpatialEmbedding
 ]

 DISAMBIGUATION_RULE =
  "When geometric space is subdivided into cells or regions to accelerate search, location, collision, visibility or other spatial operations, interpret the context as spatial partitioning."
}

CORE_CONCEPTS {

 SpatialPartitioning {
  definition = "The decomposition of a geometric domain into spatial cells or regions."
 }

 SpatialSubdivision {
  definition = "A partition or arrangement of space into geometrically meaningful cells."
 }

 Cell {
  definition = "A region of a spatial partition used as a basic unit of indexing or computation."
 }

 UniformGrid {
  definition = "A regular partition into equal-sized axis-aligned cells."
 }

 AdaptiveGrid {
  definition = "A nonuniform grid refined according to local spatial complexity or query demand."
 }

 Quadtree {
  definition = "A hierarchical two-dimensional partition recursively subdividing regions into four children."
 }

 Octree {
  definition = "A hierarchical three-dimensional partition recursively subdividing regions into eight children."
 }

 KDTree {
  definition = "A binary space-partitioning tree that recursively splits points or regions with axis-aligned hyperplanes."
 }

 BSPTree {
  definition = "A binary tree partitioning space recursively by general splitting hyperplanes."
 }

 SpatialHash {
  definition = "A mapping from spatial coordinates or cells to hash keys for near-constant-time local lookup."
 }

 BoundingVolumeHierarchy {
  definition = "A tree of nested bounding regions enclosing groups of geometric objects."
 }

 HierarchicalPartition {
  definition = "A partition organised across multiple nested levels of spatial resolution."
 }
}

RELATIONS {
 SpatialPartitioning --is_subdomain_structure_of--> ComputationalGeometry
 SpatialPartitioning --creates--> Cell
 Cell --has_boundary--> PartitionBoundary
 UniformGrid --is_special_case_of--> Grid
 AdaptiveGrid --is_special_case_of--> Grid
 Quadtree --is_special_case_of--> HierarchicalPartition
 Octree --is_special_case_of--> HierarchicalPartition
 KDTree --is_special_case_of--> SpatialIndex
 BSPTree --is_special_case_of--> SpatialIndex
 SpatialHash --is_special_case_of--> SpatialIndex
 BoundingVolumeHierarchy --supports--> SpatialSearch
 SpatialPartitioning --supports--> PointLocation
 SpatialPartitioning --supports--> RangeSearching
 SpatialPartitioning --supports--> CollisionDetection
 SpatialPartitioning --supports--> Visibility
 SpatialPartitioning --supports--> NearestNeighbour
 Refinement --increases--> LocalPartitionResolution
 Coarsening --decreases--> LocalPartitionResolution
 CellAdjacency --supports--> Traversal
}

OPERATORS {
 PARTITION(domain,strategy) :=
  set_of_cells_covering_domain_according_to_strategy

 IS_VALID_PARTITION({C_i},Omega) :=
  union_i C_i = Omega
  AND interiors_pairwise_disjoint

 LOCATE_POINT(x,Partition) :=
  cell_or_boundary_containing_x

 RANGE_QUERY(Q,Partition) :=
  cells_or_objects_intersecting_query_region_Q

 NEIGHBOUR_CELLS(C,Partition) :=
  cells_sharing_boundary_with_C

 QUADTREE_SPLIT(C) :=
  four_equal_axis_aligned_children

 OCTREE_SPLIT(C) :=
  eight_equal_axis_aligned_children

 KD_SPLIT(S,axis,value) :=
  binary_partition_by_axis_aligned_hyperplane

 BSP_SPLIT(S,H) :=
  binary_partition_by_hyperplane_H

 HASH_CELL(x,h) :=
  integer_cell_coordinates_or_hash_key_for_x

 REFINE_CELL(C) :=
  replace_C_with_children_according_to_partition_rule

 COARSEN_CHILDREN(children) :=
  replace_children_with_parent_when_allowed
}

DEFINITIONS {
 D1 = "A spatial partition covers its intended domain."
 D2 = "Cell interiors are typically disjoint."
 D3 = "Partition boundaries may be shared by adjacent cells."
 D4 = "Hierarchical partitions organise coarse-to-fine spatial resolution."
 D5 = "Quadtrees recursively partition two-dimensional regions."
 D6 = "Octrees recursively partition three-dimensional regions."
 D7 = "k-d trees use binary axis-aligned splits."
 D8 = "BSP trees permit more general splitting hyperplanes."
 D9 = "Spatial hashes trade hierarchy for direct cell-key lookup."
 D10 = "The best partition depends on dimension, geometry distribution, update frequency and query type."
}

AXIOMS {
 A1_COVERAGE:
  The union of partition cells equals the represented domain

 A2_INTERIOR_DISJOINTNESS:
  Distinct partition cells have disjoint interiors

 A3_BOUNDARY_SHARING:
  Adjacent cells may share lower-dimensional boundaries

 A4_HIERARCHY:
  In a hierarchical partition, each child is contained within its parent

 A5_REFINEMENT:
  Refinement replaces a cell with subcells whose union equals the original cell

 A6_COARSENING:
  Coarsening reverses compatible refinement while preserving domain coverage

 A7_QUERY_CORRECTNESS:
  Point-location and range-query results must be consistent with cell geometry

 A8_SPATIAL_LOCALITY:
  Partitioning should preserve or exploit spatial locality under the intended workload
}

REASONING {

 R1_PARTITION_CLASSIFICATION {
  INPUT = spatial_structure
  IDENTIFY = dimension
  IDENTIFY = regular_or_adaptive
  IDENTIFY = hierarchical_or_flat
  IDENTIFY = split_geometry
  RETURN = partition_type
 }

 R2_POINT_LOCATION {
  INPUT = [point_x,partition]
  IF hierarchical
   DESCEND = tree_using_split_tests
  ELSE
   COMPUTE = direct_cell_index_or_search
  RETURN = containing_cell_or_boundary
 }

 R3_RANGE_QUERY {
  INPUT = [query_region_Q,partition]
  TRAVERSE = cells_or_nodes_whose_bounds_intersect_Q
  PRUNE = disjoint_regions
  RETURN = candidate_cells_or_objects
 }

 R4_QUADTREE_OCTREE {
  INPUT = domain_and_refinement_rule
  WHILE cell_requires_refinement
   SUBDIVIDE = into_four_or_eight_children
  RETURN = hierarchical_partition
 }

 R5_KDTREE {
  INPUT = point_or_object_set
  CHOOSE = split_axis
  CHOOSE = split_value
  PARTITION = left_and_right_sets
  RECURSE
  RETURN = KDTree
 }

 R6_BSPTREE {
  INPUT = geometry_set
  SELECT = splitting_hyperplane
  CLASSIFY = front_back_coplanar
  SPLIT = intersecting_geometry_when_required
  RECURSE
  RETURN = BSPTree
 }

 R7_SPATIAL_HASH {
  INPUT = object_or_point
  COMPUTE = spatial_cell_coordinates
  MAP = to_hash_key
  RETURN = bucket
 }

 R8_ADAPTIVITY {
  INPUT = partition_and_error_or_density_metric
  IDENTIFY = cells_to_refine_or_coarsen
  MODIFY = hierarchy
  VERIFY = coverage_and_balance_constraints
  RETURN = adapted_partition
 }

 R9_COLLISION_QUERY {
  INPUT = moving_or_static_objects
  USE = partition_for_broad_phase_candidate_generation
  FILTER = candidate_pairs_by_shared_or_nearby_cells
  RETURN = collision_candidates
 }
}

CONSTRAINTS {
 C1 = "Dimension must be identified before selecting quadtree, octree or related structures."
 C2 = "Cell boundary ownership must follow a consistent convention."
 C3 = "Hierarchical refinement must preserve parent coverage."
 C4 = "Overlapping bounding volumes are allowed in BVHs and must not be confused with strict partitions."
 C5 = "k-d tree performance can degrade in high dimensions."
 C6 = "Uniform grids depend strongly on cell-size choice."
 C7 = "Adaptive partitions may require balancing constraints."
 C8 = "Spatial hashing requires explicit treatment of collisions in hash key space."
 C9 = "Dynamic workloads may favour different structures from static workloads."
 C10 = "Partition topology and geometric extents must remain consistent."
}

SEMANTIC_EQUIVALENCE {
 "SpatialPartitioning" <=> "SpatialSubdivisionForComputation"
 "HierarchicalPartition" <=> "RecursiveSpatialSubdivision"
 "Quadtree" <=> "FourWayRecursive2DPartition"
 "Octree" <=> "EightWayRecursive3DPartition"
 "KDTree" <=> "AxisAlignedBinarySpacePartition"
 "BSPTree" <=> "HyperplaneBinarySpacePartition"
 "SpatialHash" <=> "HashedSpatialGridIndex"
}

VALIDATION {
 V1 = "Cells cover the intended domain."
 V2 = "Cell interiors are nonoverlapping in strict partition models."
 V3 = "Hierarchy parent-child containment holds."
 V4 = "Refinement children exactly cover the parent."
 V5 = "Point-location answer matches geometric containment."
 V6 = "Range-query traversal does not omit intersecting cells."
 V7 = "Boundary conventions are consistent."
 V8 = "Adaptive balancing rules are respected when required."
 V9 = "Spatial index matches intended dimension and workload."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 SPATIAL_PARTITIONING_DEFINITION = 0.99
 POINT_LOCATION_REASONING = 0.99
 RANGE_QUERY_REASONING = 0.99
 QUADTREE_OCTREE_REASONING = 0.99
 KDTREE_REASONING = 0.98
 BSP_REASONING = 0.98
 ADAPTIVITY_REASONING = 0.98
 COLLISION_REASONING = 0.98

 POLICY =
  "Reduce confidence when dimension, boundary policy, workload, object distribution, update frequency, balancing rule or strict-partition-versus-overlapping-hierarchy model are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  SpatialPartitioningReasoning,
  ComputationalGeometryReasoning,
  SpatialIndexSelection,
  PointLocationReasoning,
  RangeQueryReasoning,
  NearestNeighbourReasoning,
  CollisionDetectionReasoning,
  VisibilityReasoning,
  AdaptiveSubdivisionReasoning,
  HierarchicalTraversal,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "spatial partitioning" -> SpatialPartitioning
  "spatial subdivision" -> SpatialSubdivision
  "uniform grid" -> UniformGrid
  "adaptive grid" -> AdaptiveGrid
  "quadtree" -> Quadtree
  "octree" -> Octree
  "k-d tree" -> KDTree
  "kd-tree" -> KDTree
  "BSP tree" -> BSPTree
  "spatial hash" -> SpatialHash
  "bounding volume hierarchy" -> BoundingVolumeHierarchy
  "BVH" -> BoundingVolumeHierarchy
 }

 INTERPRETATION_ORDER = [
  detect_spatial_partitioning_context,
  identify dimension_domain_geometry_distribution_and_workload,
  classify flat_hierarchical_regular_adaptive_or_overlapping hierarchy,
  identify point_location_range_search_nearest_neighbour_collision_visibility_or_storage goal,
  select partition_or_index structure,
  analyse traversal_update_memory_and_query tradeoffs,
  verify coverage_boundary_hierarchy_and_consistency constraints,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("spatial partitioning")
  OR computational_geometry_context_with_spatial_subdivision
  THEN activate(SpatialPartitioningOntology)

 E2:
  IF regular_2D_recursive_partition
  THEN consider Quadtree

 E3:
  IF regular_3D_recursive_partition
  THEN consider Octree

 E4:
  IF point_set_axis_aligned_binary_search
  THEN consider KDTree

 E5:
  IF geometry_split_by_general_hyperplanes
  THEN consider BSPTree

 E6:
  IF direct_local_bucket_lookup_required
  THEN consider SpatialHash

 E7:
  IF bounding_hierarchy_with_overlap_allowed
  THEN consider BoundingVolumeHierarchy

 E8:
  IF adaptive_resolution_required
  THEN enable refinement_and_coarsening rules

 E9:
  IF query_workload_known
  THEN select structure based_on query_update_memory_tradeoff
}

RECURSION {
 ENTRY = SpatialPartitioning

 EXPAND(SpatialPartitioning) -> [
  SpatialSubdivision,
  Cell,
  Grid,
  UniformGrid,
  AdaptiveGrid,
  Quadtree,
  Octree,
  KDTree,
  BSPTree,
  SpatialHash,
  BoundingVolumeHierarchy,
  VoronoiSubdivision,
  Arrangement,
  PointLocation,
  RangeSearching,
  NearestNeighbour,
  CollisionDetection,
  Visibility,
  HierarchicalPartition,
  AdaptivePartition,
  CellAdjacency,
  Refinement,
  Coarsening
 ]

 EXPAND(HierarchicalPartition) -> [
  ParentCell,
  ChildCell,
  TreeNode,
  RefinementLevel,
  Traversal,
  BoundingRegion
 ]

 EXPAND(SpatialIndex) -> [
  KDTree,
  Quadtree,
  Octree,
  BSPTree,
  SpatialHash,
  BoundingVolumeHierarchy
 ]

 EXPAND(AdaptivePartition) -> [
  RefinementCriterion,
  CoarseningCriterion,
  BalancingRule,
  ErrorIndicator,
  DensityIndicator
 ]

 STOP_CONDITION =
  "Stop when the partition type, hierarchy, cell structure, query pathway, refinement strategy, complexity tradeoff or spatial-index selection is sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Geometry"

 IMMEDIATE_CONTEXTS = [
  "Computational Geometry Ontology",
  "Mesh Ontology",
  "Voronoi Diagram Ontology",
  "Point Location Ontologies"
 ]

 RELATED_ONTOLOGIES = [
  "Computational Geometry",
  "Computational Geometry Ontology",
  "Mesh Ontology",
  "Voronoi Diagram Ontology",
  "Delaunay Triangulation Ontology",
  "Topology Ontology",
  "Coordinate Geometry Ontology",
  "Spatial Data Structure Ontologies",
  "Algorithm Ontologies",
  "Collision Detection Ontologies"
 ]

 ROUTE_RULES = [
  "Spatial Partitioning -> Computational Geometry Ontology for parent algorithmic semantics",
  "Spatial Partitioning -> Mesh for cell-complex discretisation",
  "Spatial Partitioning -> Voronoi Diagram for nearest-site subdivisions",
  "Spatial Partitioning -> Topology for adjacency and incidence consistency",
  "Spatial Partitioning -> Coordinate Geometry for split planes and bounds",
  "Spatial Partitioning -> Spatial Data Structures for indexing and query implementation",
  "Spatial Partitioning -> Algorithms for traversal and complexity",
  "Spatial Partitioning -> Collision Detection for broad-phase acceleration"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible partition structures, query models or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"

 RULES = [
  "Preserve domain-decomposition semantics.",
  "Preserve cell coverage and interior-disjointness for strict partitions.",
  "Preserve distinction between strict partitions and overlapping hierarchies.",
  "Preserve dimension-aware structure selection.",
  "Preserve hierarchy parent-child containment.",
  "Preserve refinement/coarsening semantics.",
  "Preserve workload-aware query tradeoffs.",
  "Preserve machine-readable spatial-partitioning semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "Spatial partitioning decomposes a geometric domain into cells or regions to support efficient spatial computation."

 COVERAGE_SUMMARY =
  "A valid strict partition covers the target domain with pairwise disjoint cell interiors."

 HIERARCHY_SUMMARY =
  "Hierarchical partitions organise nested spatial cells across multiple levels."

 QUADTREE_SUMMARY =
  "A quadtree recursively subdivides two-dimensional regions into four children."

 OCTREE_SUMMARY =
  "An octree recursively subdivides three-dimensional regions into eight children."

 KDTREE_SUMMARY =
  "A k-d tree recursively partitions space using axis-aligned binary splits."

 BSP_SUMMARY =
  "A BSP tree recursively partitions space using general splitting hyperplanes."

 HASH_SUMMARY =
  "Spatial hashing maps spatial cells to hash keys for fast local lookup."

 QUERY_SUMMARY =
  "Spatial partitions accelerate point location, range search, nearest-neighbour, visibility and collision queries."
}

FLOW {
 INPUT
 -> detect_spatial_partitioning_context
 -> identify dimension_domain_geometry_distribution_updates_and_query_workload
 -> classify strict_partition_or_overlapping_hierarchy
 -> identify grid_quadtree_octree_kdtree_BSP_spatial_hash_BVH_or_other structure
 -> identify point_location_range_search_nearest_neighbour_collision_visibility_or_storage goal
 -> select partition_parameters_and_traversal strategy
 -> verify coverage_boundary_hierarchy_consistency_and_performance constraints
 -> route to computational_geometry mesh Voronoi topology coordinate spatial_data_structure algorithm_or_collision ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Spatial Partitioning Ontology defines geometric subdivision strategies used to organise space for efficient computation. It supports uniform and adaptive grids, quadtrees, octrees, k-d trees, BSP trees, spatial hashing, bounding-volume hierarchies, Voronoi subdivisions, hierarchical refinement, adjacency, point location, range searching, nearest-neighbour search, visibility and collision detection while preserving domain coverage and structural consistency."
}

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

}

END_FLOW