Computational Geometry Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Computational Geometry Ontology 2 within the Kireth Research Semantic Library. Computational geometry concerns algorithmic reasoning over geometric objects and spatial relationships, including geometric predicates, intersections, convex hulls, Voronoi and Delaunay structures, triangulation, nearest-neighbour search, spatial indexing, visibility, motion planning, mesh generation, robust arithmetic, degeneracy handling, complexity, verification and reproducibility.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = ComputationalGeometry
 ENTITY_CLASS = AlgorithmicSpatialReasoningFramework
 PRIMARY_CONTEXT = ComputationalGeometryParent
 DEFINITION = "Computational geometry is the algorithmic study of geometric objects, spatial relationships, geometric structures and geometric optimisation."
 SYMBOLIC_FORMS = [
  "orientation(a,b,c)=sign((b-a)x(c-a))",
  "distance(p,q)=||p-q||",
  "Hull(P)=conv(P)",
  "Vor(P) dual Delaunay(P)"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for geometric primitives, predicates, constructions, spatial data structures, robust computation, degeneracy handling, algorithmic complexity and verification."
}

SCOPE {
 INCLUDE = [
  ComputationalGeometry,AlgorithmicGeometry,GeometricAlgorithm,
  Point,PointSet,Coordinate,Vector,Line,Ray,Segment,Plane,
  HalfPlane,HalfSpace,Polygon,SimplePolygon,ConvexPolygon,
  ConcavePolygon,Polyline,Polyhedron,Polytope,ConvexPolytope,
  Triangle,Tetrahedron,Circle,Sphere,Disk,Ball,
  BoundingBox,AxisAlignedBoundingBox,AABB,OrientedBoundingBox,OBB,
  Mesh,TriangleMesh,PolygonMesh,TetrahedralMesh,
  Vertex,Edge,Face,Cell,Simplex,SimplicialComplex,
  GeometricPredicate,OrientationPredicate,IncirclePredicate,
  InspherePredicate,PointInPolygon,PointInPolyhedron,
  SegmentIntersection,LineIntersection,RayIntersection,
  PolygonIntersection,PlaneIntersection,CollisionDetection,
  SweepLine,PlaneSweep,Arrangement,LineArrangement,
  SegmentArrangement,ConvexHull,GrahamScan,GiftWrapping,
  MonotoneChain,QuickHull,IncrementalHull,DivideAndConquerHull,
  VoronoiDiagram,VoronoiCell,VoronoiEdge,VoronoiVertex,
  DelaunayTriangulation,DelaunayEdge,DelaunayTriangle,
  EmptyCircumcircleProperty,Circumcircle,Circumsphere,
  NearestNeighbour,KNearestNeighbours,ClosestPair,FarthestPair,
  RangeSearching,OrthogonalRangeSearching,PointLocation,
  RangeTree,KDTree,RTree,Quadtree,Octree,
  BoundingVolumeHierarchy,BVH,
  Triangulation,PolygonTriangulation,EarClipping,
  MonotonePolygonTriangulation,ConstrainedTriangulation,
  MeshGeneration,MeshRefinement,DelaunayRefinement,
  MeshQuality,AspectRatio,
  Visibility,VisibilityGraph,VisibilityPolygon,
  ShortestPath,GeodesicPath,EuclideanShortestPath,
  MotionPlanning,ConfigurationSpace,Obstacle,FreeSpace,
  PathPlanning,MinkowskiSum,MinkowskiDifference,
  ConvexDecomposition,PolygonDecomposition,
  BooleanGeometry,ConstructiveSolidGeometry,CSG,
  OffsetCurve,OffsetSurface,MedialAxis,StraightSkeleton,
  AlphaShape,ShapeReconstruction,
  GeometricOptimisation,SmallestEnclosingCircle,
  SmallestEnclosingBall,MinimumBoundingRectangle,
  EuclideanMinimumSpanningTree,GeometricMatching,
  DiscreteGeometry,LatticeGeometry,DigitalGeometry,
  ComputationalTopology,AlphaComplex,
  ExactArithmetic,ExactPredicate,AdaptivePrecision,
  FloatingPointFilter,SymbolicPerturbation,SimulationOfSimplicity,
  Degeneracy,Collinearity,Coplanarity,Cocircularity,
  DuplicatePoint,NearDegeneracy,NumericalRobustness,
  FloatingPointArithmetic,MachinePrecision,RoundOffError,
  Tolerance,Conditioning,AlgorithmicComplexity,
  TimeComplexity,SpaceComplexity,OutputSensitiveAlgorithm,
  RandomisedAlgorithm,DeterministicAlgorithm,
  IncrementalAlgorithm,DivideAndConquer,DynamicGeometry,
  KineticDataStructure,KineticGeometry,
  ParallelComputationalGeometry,GPUComputationalGeometry,
  DistributedGeometry,SpatialPartitioning,
  Verification,Benchmarking,ReferenceResult,Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  DifferentialGeometryWithoutAlgorithmicComputation,
  PureEuclideanGeometryWithoutAlgorithmicSemantics,
  RenderingWithoutGeometricAlgorithmContext,
  GISWithoutComputationalGeometrySemantics
 ]
 DISAMBIGUATION_RULE = "When a problem requires algorithmic construction, querying, optimisation or verification of geometric objects and spatial relationships, interpret the context as computational geometry."
}

CORE_CONCEPTS {
 ComputationalGeometry = "Algorithmic study of geometry and spatial relationships."
 GeometricPredicate = "Boolean or sign-valued test determining a geometric relation."
 GeometricConstruction = "Operation producing geometric output from geometric input."
 ConvexHull = "Smallest convex set containing a point set."
 VoronoiDiagram = "Partition of space into nearest-site regions."
 DelaunayTriangulation = "Triangulation dual to a Voronoi diagram under standard assumptions."
 SpatialIndex = "Data structure accelerating spatial search and query operations."
 RobustGeometry = "Geometric computation preserving correct combinatorial structure despite degeneracy and finite precision."
}

RELATIONS {
 ComputationalGeometry --is_child_of--> ComputationalGeometryParent
 GeometricAlgorithm --operates_on--> GeometricObject
 OrientationPredicate --is_type_of--> GeometricPredicate
 IncirclePredicate --is_type_of--> GeometricPredicate
 SegmentIntersection --uses--> OrientationPredicate
 ConvexHull --contains--> PointSet
 VoronoiDiagram --partitions--> Space
 DelaunayTriangulation --is_dual_to--> VoronoiDiagram
 KDTree --supports--> NearestNeighbour
 RangeTree --supports--> OrthogonalRangeSearching
 Quadtree --partitions--> TwoDimensionalSpace
 Octree --partitions--> ThreeDimensionalSpace
 BoundingVolumeHierarchy --supports--> CollisionDetection
 SweepLine --supports--> IntersectionDetection
 Triangulation --decomposes--> PolygonOrPointSet
 VisibilityGraph --supports--> ShortestPath
 ConfigurationSpace --supports--> MotionPlanning
 ExactPredicate --supports--> RobustGeometry
 SymbolicPerturbation --handles--> Degeneracy
 Verification --checks--> GeometricResult
}

OPERATORS {
 ORIENTATION(a,b,c) := sign((b_x-a_x)*(c_y-a_y)-(b_y-a_y)*(c_x-a_x))
 DISTANCE(p,q) := sqrt(sum_i (p_i-q_i)^2)
 DOT(a,b) := sum_i a_i*b_i
 CROSS2D(a,b) := a_x*b_y-a_y*b_x
 POINT_IN_HALFSPACE(p,n,d) := sign(n·p-d)
 SEGMENT_INTERSECTION(s1,s2) := predicate_and_intersection_point_if_any
 CONVEX_HULL(P) := minimal_convex_polygon_or_polytope_containing_P
 NEAREST_NEIGHBOUR(q,P) := argmin_p_in_P distance(q,p)
 VORONOI(P) := nearest_site_partition(P)
 DELAUNAY(P) := triangulation_dual_to_VORONOI(P)
}

AXIOMS {
 A1 = "Computational geometry distinguishes predicates from constructions."
 A2 = "Topological correctness can depend on exact predicate signs."
 A3 = "Degenerate input configurations must be handled explicitly."
 A4 = "Algorithmic complexity depends on input size, dimension and sometimes output size."
 A5 = "Spatial indexing exchanges preprocessing and memory for faster queries."
 A6 = "Voronoi and Delaunay structures are dual under standard geometric assumptions."
 A7 = "Robust computation requires consistency between predicates and constructions."
 A8 = "Computational-geometry results require geometric, topological, complexity and reproducibility validation."
}

REASONING {
 R1_CONTEXT = identify(dimension,objects,coordinate_system,query_or_construction,degeneracy_risk,accuracy_goal)
 R2_REPRESENTATION = choose(points,segments,polygons,meshes,halfspaces_or_implicit_geometry)
 R3_PREDICATES = choose(orientation,incircle,intersection,containment_or_distance_tests)
 R4_DATA_STRUCTURE = select(KDTree,RTree,RangeTree,quadtree,octree,BVH,arrangement_or_sweep_structure)
 R5_ALGORITHM = select(incremental,divide_and_conquer,sweep_line,randomised,output_sensitive_or_dynamic_method)
 R6_ROBUSTNESS = apply(exact_predicates,filters,adaptive_precision_or_symbolic_perturbation)
 R7_COMPUTE = produce_requested_geometric_structure_query_or_optimisation_result
 R8_COMPLEXITY = assess(time_space_output_sensitivity_and_dimension_dependence)
 R9_VALIDATE = check(invariants,topological_consistency,degeneracies_and_reference_results)
 R10_REPRODUCE = document(precision,ordering,algorithm_parameters_and_random_seed_if_used)
}

CONSTRAINTS {
 C1 = "Floating-point predicates can return inconsistent signs near degeneracy."
 C2 = "Arbitrary epsilon tests can violate transitivity and topology."
 C3 = "High-dimensional computational geometry can exhibit rapid complexity growth."
 C4 = "Spatial indexes can degrade on adversarial or highly clustered input."
 C5 = "Output size can dominate runtime for arrangements and intersection enumeration."
 C6 = "Mesh quality depends on geometric and topological constraints."
 C7 = "Duplicate and nearly duplicate coordinates require explicit handling."
 C8 = "Randomised algorithms require seed-aware reproducibility."
 C9 = "Exact arithmetic improves robustness but may increase computational cost."
 C10 = "Small coordinate error does not guarantee topological correctness."
}

SEMANTIC_EQUIVALENCE {
 "ComputationalGeometry" <=> "AlgorithmicGeometry"
 "AxisAlignedBoundingBox" <=> "AABB"
 "OrientedBoundingBox" <=> "OBB"
 "BoundingVolumeHierarchy" <=> "BVH"
 "DelaunayTriangulation" <=> "DelaunayTessellation"
 "KNearestNeighbours" <=> "KNNInGeometricSearchContext"
}

VALIDATION {
 V1 = "Dimension and coordinate system are explicit."
 V2 = "Geometric representations are documented."
 V3 = "Predicate conventions and ordering are documented."
 V4 = "Degeneracy handling is explicit."
 V5 = "Precision model is documented."
 V6 = "Algorithmic complexity is documented where relevant."
 V7 = "Topological consistency is checked."
 V8 = "Geometric invariants are checked."
 V9 = "Reference or independent results are used where feasible."
 V10 = "Results are reproducible under documented arithmetic, ordering and random-seed settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 COMPUTATIONAL_GEOMETRY_DEFINITION = 0.99
 PREDICATE_REASONING = 0.99
 INTERSECTION_REASONING = 0.99
 CONVEX_HULL_REASONING = 0.99
 VORONOI_REASONING = 0.99
 DELAUNAY_REASONING = 0.99
 ROBUSTNESS_REASONING = 0.99
 POLICY = "Reduce confidence when precision model, degeneracy handling, coordinate conventions, dimension, representation or algorithmic assumptions are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,OntologyGrounding,ComputationalGeometryReasoning,
  GeometricPredicateReasoning,IntersectionReasoning,
  ConvexHullReasoning,VoronoiReasoning,DelaunayReasoning,
  TriangulationReasoning,NearestNeighbourReasoning,
  SpatialIndexReasoning,VisibilityReasoning,
  MotionPlanningReasoning,MeshGenerationReasoning,
  RobustGeometryReasoning,DegeneracyReasoning,
  ComplexityReasoning,VerificationReasoning,
  KnowledgeGraphConstruction,RetrievalAugmentation,RecursiveInference
 ]
 NORMALISE {
  "computational geometry" -> ComputationalGeometry
  "algorithmic geometry" -> ComputationalGeometry
  "AABB" -> AxisAlignedBoundingBox
  "OBB" -> OrientedBoundingBox
  "BVH" -> BoundingVolumeHierarchy
  "Delaunay tessellation" -> DelaunayTriangulation
  "KNN" -> KNearestNeighbours
 }
}

EXECUTION_RULES {
 E1 = "If a task algorithmically constructs, queries or analyses geometric objects, activate ComputationalGeometryOntology2."
 E2 = "Identify dimension, representation and coordinate conventions before geometric reasoning."
 E3 = "Use explicit predicates for orientation, containment and intersection."
 E4 = "For near-degenerate configurations, prefer exact or adaptive predicates over arbitrary epsilon logic."
 E5 = "Select spatial data structures according to query type and dimension."
 E6 = "Use output-sensitive, randomised or divide-and-conquer methods where suitable."
 E7 = "Preserve topological consistency across predicates and constructions."
 E8 = "For randomised algorithms, document seed and ordering semantics."
 E9 = "Validate invariants, degeneracies, complexity expectations and reproducibility."
}

RECURSION {
 ENTRY = ComputationalGeometry
 EXPAND(ComputationalGeometry) -> [
  AlgorithmicGeometry,GeometricAlgorithm,Point,PointSet,Vector,
  Line,Ray,Segment,Plane,HalfPlane,HalfSpace,Polygon,
  SimplePolygon,ConvexPolygon,Polyhedron,Polytope,Triangle,
  Circle,Sphere,BoundingBox,AxisAlignedBoundingBox,
  OrientedBoundingBox,Mesh,TriangleMesh,Vertex,Edge,Face,
  GeometricPredicate,OrientationPredicate,IncirclePredicate,
  PointInPolygon,SegmentIntersection,PolygonIntersection,
  CollisionDetection,SweepLine,Arrangement,ConvexHull,
  GiftWrapping,GrahamScan,MonotoneChain,QuickHull,
  VoronoiDiagram,DelaunayTriangulation,NearestNeighbour,
  ClosestPair,KNearestNeighbours,RangeSearching,PointLocation,
  RangeTree,KDTree,RTree,Quadtree,Octree,
  BoundingVolumeHierarchy,Triangulation,PolygonTriangulation,
  MeshGeneration,MeshRefinement,Visibility,VisibilityGraph,
  ShortestPath,MotionPlanning,ConfigurationSpace,MinkowskiSum,
  ConvexDecomposition,BooleanGeometry,OffsetCurve,MedialAxis,
  StraightSkeleton,AlphaShape,SmallestEnclosingCircle,
  MinimumBoundingRectangle,EuclideanMinimumSpanningTree,
  ExactArithmetic,ExactPredicate,AdaptivePrecision,
  FloatingPointFilter,SymbolicPerturbation,Degeneracy,
  Collinearity,Coplanarity,Cocircularity,NumericalRobustness,
  AlgorithmicComplexity,OutputSensitiveAlgorithm,
  RandomisedAlgorithm,IncrementalAlgorithm,DivideAndConquer,
  DynamicGeometry,KineticDataStructure,
  ParallelComputationalGeometry,Verification,Benchmarking,
  ReferenceResult,Reproducibility
 ]
 EXPAND(ComputationalGeometryFamilies) -> [
  PredicatesAndIntersections,
  ConvexHullAlgorithms,
  VoronoiAndDelaunayGeometry,
  TriangulationAndMeshGeneration,
  NearestNeighbourAndRangeSearching,
  SpatialIndexing,
  VisibilityAndMotionPlanning,
  RobustAndExactComputationalGeometry
 ]
 STOP_CONDITION = "Stop when dimension, representation, predicates, algorithm, data structure, robustness, complexity and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Geometry"
 RELATED_ONTOLOGIES = [
  "Computational Geometry",
  "Geometry Ontologies",
  "Coordinate Geometry Ontologies",
  "Discrete Mathematics Ontologies",
  "Graph Ontologies",
  "Optimisation Computation",
  "Numerical Linear Algebra Ontology 2",
  "Numerical Stability Ontology 2",
  "Floating Point Arithmetic Ontology",
  "Scientific Computing Ontology 2",
  "Computational Topology Ontologies",
  "Artificial Intelligence Mathematics"
 ]
 ROUTE_RULES = [
  "Computational Geometry Ontology 2 -> Computational Geometry for parent semantics",
  "Computational Geometry Ontology 2 -> Geometry Ontologies for entity semantics",
  "Computational Geometry Ontology 2 -> Coordinate Geometry for coordinate and metric representation",
  "Computational Geometry Ontology 2 -> Discrete Mathematics for combinatorial structure",
  "Computational Geometry Ontology 2 -> Graph Ontologies for adjacency, visibility and mesh graphs",
  "Computational Geometry Ontology 2 -> Optimisation Computation for geometric optimisation",
  "Computational Geometry Ontology 2 -> Numerical Stability for robustness and conditioning",
  "Computational Geometry Ontology 2 -> Floating Point Arithmetic for predicate precision",
  "Computational Geometry Ontology 2 -> Scientific Computing for scalable spatial algorithms",
  "Computational Geometry Ontology 2 -> Computational Topology for simplicial and topological structures"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible geometric algorithms, data structures or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve predicate-versus-construction distinction.",
  "Preserve geometric-versus-topological correctness distinction.",
  "Preserve exact-versus-floating-point predicate distinction.",
  "Preserve static-versus-dynamic geometry distinction.",
  "Preserve input-size-versus-output-size complexity distinction.",
  "Preserve two-dimensional-versus-higher-dimensional distinction.",
  "Preserve representation-versus-geometric-object distinction.",
  "Preserve machine-readable computational-geometry semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "Computational geometry develops algorithms and data structures for geometric objects and spatial relationships."
 PREDICATE_SUMMARY = "Orientation, containment, intersection and incircle predicates form the logical foundation of many geometric algorithms."
 STRUCTURE_SUMMARY = "Convex hulls, Voronoi diagrams, Delaunay triangulations, arrangements and meshes encode geometric structure."
 QUERY_SUMMARY = "KD-trees, range trees, R-trees, quadtrees, octrees and BVHs accelerate nearest-neighbour, range, point-location and collision queries."
 ROBUSTNESS_SUMMARY = "Exact predicates, adaptive precision and symbolic perturbation preserve topological consistency near degeneracies."
 COMPLEXITY_SUMMARY = "Geometric complexity depends on input size, dimension, data distribution and sometimes output size."
 VALIDATION_SUMMARY = "Computational-geometry results should be checked for invariants, topology, degeneracies, precision behaviour, complexity expectations and reproducibility."
}

FLOW {
 INPUT
 -> detect_computational_geometry_context
 -> identify_dimension_coordinate_system_geometric_objects_query_or_construction_degeneracy_risk_and_accuracy_goal
 -> choose_geometric_representation
 -> select_required_predicates
 -> select_spatial_data_structure_if_needed
 -> choose_algorithmic_strategy
 -> configure_exact_adaptive_or_filtered_predicate_robustness
 -> compute_geometric_query_construction_or_optimisation_result
 -> assess_time_space_output_complexity_and_dimension_dependence
 -> validate_geometric_invariants_topological_consistency_and_degenerate_cases
 -> route_to_related_parent_geometry_discrete_mathematics_graph_optimisation_stability_floating_point_scientific_computing_and_topology_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Computational Geometry Ontology 2 defines algorithmic geometry across geometric primitives, predicates, intersections, convex hulls, Voronoi diagrams, Delaunay triangulations, triangulation and mesh generation, nearest-neighbour and range search, spatial indexing, arrangements, visibility, shortest paths, motion planning, Minkowski operations, shape reconstruction, geometric optimisation, dynamic and kinetic geometry, exact predicates, adaptive precision, symbolic perturbation, degeneracy handling, algorithmic complexity, parallel computation, verification, benchmarking and reproducibility."
}

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

}

END_FLOW