Computational Geometry

AI INTERPRETATION NOTE
This Flow Algebra defines the Computational Geometry parent ontology within the Kireth Research Semantic Library. Computational geometry studies algorithms and data structures for geometric objects, spatial relationships and geometric optimisation. This ontology supports points, lines, segments, polygons, meshes, convex hulls, Voronoi diagrams, Delaunay triangulations, nearest-neighbour problems, intersection detection, arrangements, visibility, motion planning, spatial indexing, robustness, degeneracy handling, exact predicates, numerical precision, algorithmic complexity, verification and reproducibility.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = ComputationalGeometry
 ENTITY_CLASS = AlgorithmicGeometryFramework
 PRIMARY_CONTEXT = ComputationalMathematicsOntologies
 DEFINITION = "Computational geometry is the study and implementation of algorithms for geometric objects, spatial structures, geometric queries and optimisation problems."
 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 algorithms, data structures, robustness, complexity and verification."
}

SCOPE {
 INCLUDE = [
  ComputationalGeometry,AlgorithmicGeometry,GeometricAlgorithm,
  Point,PointSet,Vector,Coordinate,CartesianCoordinate,
  HomogeneousCoordinate,Line,Ray,Segment,Plane,HalfPlane,
  HalfSpace,Polygon,SimplePolygon,ConvexPolygon,ConcavePolygon,
  Polyline,PolylineSegment,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,
  PointOnSegment,SegmentIntersection,LineIntersection,
  PolygonIntersection,PlaneIntersection,RayIntersection,
  CollisionDetection,IntersectionDetection,
  SweepLine,PlaneSweep,EventQueue,StatusStructure,
  Arrangement,LineArrangement,SegmentArrangement,
  ConvexHull,GiftWrapping,GrahamScan,MonotoneChain,
  QuickHull,IncrementalHull,DivideAndConquerHull,
  VoronoiDiagram,VoronoiCell,VoronoiVertex,VoronoiEdge,
  DelaunayTriangulation,DelaunayEdge,DelaunayTriangle,
  EmptyCircumcircleProperty,Circumcircle,Circumsphere,
  NearestNeighbour,ClosestPair,FarthestPair,
  KNearestNeighbours,RangeSearching,OrthogonalRangeSearching,
  SpatialQuery,PointLocation,PlanarPointLocation,
  RangeTree,KDTree,KDTreeSearch,RTree,Quadtree,Octree,
  BoundingVolumeHierarchy,BVH,
  Triangulation,PolygonTriangulation,EarClipping,
  MonotonePolygonTriangulation,ConstrainedTriangulation,
  MeshGeneration,MeshRefinement,DelaunayRefinement,
  QualityMesh,MeshQuality,AspectRatio,
  Visibility,VisibilityGraph,VisibilityPolygon,
  ArtGalleryProblem,ShortestPath,GeodesicPath,
  EuclideanShortestPath,MotionPlanning,ConfigurationSpace,
  RobotGeometry,Obstacle,FreeSpace,PathPlanning,
  MinkowskiSum,MinkowskiDifference,
  ConvexDecomposition,PolygonDecomposition,
  BooleanGeometry,ConstructiveSolidGeometry,CSG,
  OffsetCurve,OffsetSurface,MedialAxis,Skeleton,
  StraightSkeleton,AlphaShape,ShapeReconstruction,
  GeometricOptimisation,SmallestEnclosingCircle,
  SmallestEnclosingBall,MinimumBoundingRectangle,
  MinimumSpanningTree,EuclideanMinimumSpanningTree,
  GeometricMatching,FacilityLocation,
  DiscreteGeometry,LatticeGeometry,DigitalGeometry,
  ComputationalTopology,AlphaComplex,
  RobustGeometry,ExactArithmetic,ExactPredicate,
  AdaptivePrecision,FloatingPointFilter,
  SymbolicPerturbation,SimulationOfSimplicity,
  Degeneracy,Collinearity,Coplanarity,Cocircularity,
  DuplicatePoint,NearDegeneracy,NumericalRobustness,
  FloatingPointArithmetic,MachinePrecision,RoundOffError,
  EpsilonComparison,Tolerance,Conditioning,
  AlgorithmicComplexity,TimeComplexity,SpaceComplexity,
  OutputSensitiveAlgorithm,RandomisedAlgorithm,
  DeterministicAlgorithm,IncrementalAlgorithm,
  DivideAndConquer,DynamicGeometry,KineticDataStructure,
  DynamicPointSet,KineticGeometry,
  ParallelComputationalGeometry,GPUComputationalGeometry,
  DistributedGeometry,SpatialPartitioning,
  Verification,Benchmarking,ReferenceResult,
  Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  DifferentialGeometryWithoutAlgorithmicComputation,
  PureEuclideanGeometryWithoutAlgorithmicSemantics,
  ComputerGraphicsRenderingWithoutGeometricAlgorithmContext,
  GeographicInformationSystemsWithoutComputationalGeometrySemantics
 ]
 DISAMBIGUATION_RULE = "When the task involves algorithmic construction, querying, optimisation or analysis of geometric objects and spatial relationships, interpret the context as computational geometry."
}

CORE_CONCEPTS {
 ComputationalGeometry = "Algorithmic study of geometric objects and spatial relationships."
 GeometricPredicate = "Boolean or sign-valued test determining a geometric relation."
 GeometricConstruction = "Operation producing a new geometric object from existing objects."
 ConvexHull = "Smallest convex set containing a given point set."
 VoronoiDiagram = "Partition of space by nearest-site regions."
 DelaunayTriangulation = "Triangulation dual to a Voronoi diagram under standard general-position assumptions."
 SpatialIndex = "Data structure accelerating spatial queries."
 RobustGeometry = "Use of numerically reliable predicates and constructions despite degeneracy and finite precision."
}

RELATIONS {
 ComputationalGeometry --is_child_of--> ComputationalMathematicsOntologies
 GeometricAlgorithm --operates_on--> GeometricObject
 OrientationPredicate --is_type_of--> GeometricPredicate
 IncirclePredicate --is_type_of--> GeometricPredicate
 ConvexHull --contains--> InputPointSet
 VoronoiDiagram --partitions--> Space
 DelaunayTriangulation --is_dual_to--> VoronoiDiagram
 KDTree --supports--> NearestNeighbour
 RangeTree --supports--> RangeSearching
 Quadtree --partitions--> TwoDimensionalSpace
 Octree --partitions--> ThreeDimensionalSpace
 BVH --supports--> CollisionDetection
 SweepLine --supports--> IntersectionDetection
 Triangulation --decomposes--> Polygon
 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 separates geometric predicates from geometric constructions."
 A2 = "Topological correctness can depend on exact sign decisions even when coordinates are floating-point."
 A3 = "Degenerate configurations must be handled explicitly rather than assumed absent."
 A4 = "Geometric algorithm complexity depends on input size, dimension and sometimes output size."
 A5 = "Spatial indexing trades preprocessing and memory for faster queries."
 A6 = "Voronoi and Delaunay structures are dual under standard geometric assumptions."
 A7 = "Robust geometric algorithms require consistency between predicates and constructions."
 A8 = "Computational-geometry results require geometric, topological, complexity and reproducibility validation."
}

REASONING {
 R1_CONTEXT = identify(dimension,geometric_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(sweep_structure,KDTree,RTree,quadtree,octree,BVH_or_arrangement)
 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_CONSTRUCTION = compute_requested_geometric_structure_or_query_result
 R8_COMPLEXITY = assess(time_space_output_sensitivity_and_dimension_dependence)
 R9_VALIDATE = check(topological_consistency,predicate_consistency,degeneracy_cases_and_reference_results)
 R10_REPRODUCE = document_coordinate_precision_algorithm_parameters_and_ordering_rules
}

CONSTRAINTS {
 C1 = "Floating-point predicates can return inconsistent signs near degeneracy."
 C2 = "Epsilon tests can break transitivity and topology when used indiscriminately."
 C3 = "High-dimensional geometry can suffer rapid complexity growth."
 C4 = "Spatial indexes can degrade on adversarial or highly clustered data."
 C5 = "Output size can dominate runtime in arrangements and intersection problems."
 C6 = "Mesh quality depends on geometric and topological constraints."
 C7 = "Duplicate or nearly duplicate coordinates require explicit handling."
 C8 = "Randomised algorithms require seed-aware reproducibility."
 C9 = "Exact arithmetic improves robustness but can increase computational cost."
 C10 = "Topologically valid output is not guaranteed by small coordinate error alone."
}

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

VALIDATION {
 V1 = "Dimension and coordinate system are explicit."
 V2 = "Geometric object representations are documented."
 V3 = "Predicate conventions and orientation 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 where applicable."
 V9 = "Reference or independently computed 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
 CONVEX_HULL_REASONING = 0.99
 VORONOI_REASONING = 0.99
 DELAUNAY_REASONING = 0.99
 SPATIAL_INDEX_REASONING = 0.98
 ROBUSTNESS_REASONING = 0.99
 POLICY = "Reduce confidence when coordinate precision, degeneracy handling, orientation 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 ComputationalGeometry."
 E2 = "Identify dimension, representation and coordinate conventions before geometric reasoning."
 E3 = "Use explicit geometric 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 or randomised algorithms where they improve asymptotic or practical performance."
 E7 = "Preserve topological consistency across predicates and constructions."
 E8 = "For randomised algorithms, document random seed and ordering semantics."
 E9 = "Validate geometric 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) -> [
  GeometricPredicatesAndIntersections,
  ConvexHullAlgorithms,
  VoronoiAndDelaunayGeometry,
  TriangulationAndMeshGeneration,
  NearestNeighbourAndRangeSearching,
  SpatialDataStructures,
  VisibilityAndMotionPlanning,
  RobustAndExactComputationalGeometry
 ]
 STOP_CONDITION = "Stop when dimension, representation, predicates, algorithm, data structure, robustness, complexity and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Mathematics Ontologies"
 RELATED_ONTOLOGIES = [
  "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 -> Geometry Ontologies for geometric entity semantics",
  "Computational Geometry -> Coordinate Geometry for coordinate and metric representations",
  "Computational Geometry -> Discrete Mathematics for combinatorial structure",
  "Computational Geometry -> Graph Ontologies for adjacency, visibility and mesh graphs",
  "Computational Geometry -> Optimisation Computation for geometric optimisation",
  "Computational Geometry -> Numerical Linear Algebra for coordinate transformations and geometric systems",
  "Computational Geometry -> Numerical Stability for robustness and conditioning",
  "Computational Geometry -> Floating Point Arithmetic for predicate precision",
  "Computational Geometry -> Scientific Computing for large-scale spatial algorithms",
  "Computational Geometry -> 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, spatial relationships and geometric optimisation."
 PREDICATE_SUMMARY = "Orientation, containment, intersection and incircle predicates form the logical basis 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 protect topological consistency near degenerate configurations."
 COMPLEXITY_SUMMARY = "Geometric complexity depends on input size, dimension, data distribution and often output size."
 VALIDATION_SUMMARY = "Computational-geometry results should be checked for geometric 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_geometry_discrete_mathematics_graph_optimisation_linear_algebra_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 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, robust 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-V1"
}

}

END_FLOW