Computational Geometry Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the core Computational Geometry Ontology within the Kireth Research Semantic Library. Computational geometry studies algorithms and data structures for geometric objects and spatial problems. This ontology acts as the central semantic node beneath the Computational Geometry parent layer and supports geometric predicates, convex hulls, proximity, intersection, polygon processing, Voronoi diagrams, Delaunay triangulations, point location, arrangements, spatial indexing, visibility, motion planning, numerical robustness and algorithmic complexity.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = ComputationalGeometryOntology
 ENTITY_CLASS = GeometricAlgorithmOntology
 PRIMARY_CONTEXT = ComputationalGeometry
 DEFINITION = "Computational geometry is the branch of mathematics concerned with algorithms, data structures and complexity for solving geometric and spatial problems."
 SEMANTIC_ROLE = "Provides the core machine-readable framework for classifying geometric problems, selecting algorithms and predicates, analysing complexity and ensuring robust geometric computation."
}

SCOPE {
 INCLUDE = [
  GeometricAlgorithm,
  GeometricProblem,
  GeometricDataStructure,
  GeometricPredicate,
  PointSet,
  SegmentSet,
  Polygon,
  Polyhedron,
  ConvexHull,
  ClosestPair,
  NearestNeighbour,
  SegmentIntersection,
  PointInPolygon,
  PointLocation,
  VoronoiDiagram,
  DelaunayTriangulation,
  PolygonTriangulation,
  Arrangement,
  SweepLineAlgorithm,
  DivideAndConquer,
  IncrementalAlgorithm,
  RandomisedAlgorithm,
  KDTree,
  Quadtree,
  BSPTree,
  RangeTree,
  RTree,
  Visibility,
  MotionPlanning,
  RobustPredicate,
  ExactArithmetic,
  AdaptivePrecision,
  Degeneracy,
  GeneralPosition,
  Complexity
 ]

 EXCLUDE_AS_PRIMARY = [
  RenderingPipelineWithoutGeometricAlgorithmicGoal,
  GenericNumericalAnalysisWithoutGeometry,
  PureGraphAlgorithmsWithoutSpatialEmbedding,
  ContinuousGeometryWithoutComputationalObjective
 ]

 DISAMBIGUATION_RULE =
  "When the task asks how to algorithmically compute, classify, search, intersect, triangulate, locate, decompose or optimise geometric structures, interpret it as computational geometry."
}

CORE_CONCEPTS {

 ComputationalGeometryOntology {
  definition = "The ontology organising algorithmic problems, predicates, structures and complexity in computational geometry."
 }

 GeometricProblem {
  definition = "A computational task whose inputs or outputs are geometric objects or spatial relations."
 }

 GeometricAlgorithm {
  definition = "A finite computational procedure for solving a geometric problem."
 }

 GeometricDataStructure {
  definition = "A data structure designed to support efficient spatial queries or updates."
 }

 GeometricPredicate {
  definition = "A discrete geometric decision whose output determines combinatorial structure."
 }

 ConvexHull {
  definition = "The minimal convex set containing a given point set."
 }

 ClosestPair {
  definition = "The pair of distinct input points with minimum pairwise distance."
 }

 SegmentIntersection {
  definition = "The problem of determining whether, where or how line segments intersect."
 }

 VoronoiDiagram {
  definition = "A nearest-site subdivision of space."
 }

 DelaunayTriangulation {
  definition = "A triangulation dual to the Voronoi diagram under the chosen metric and general-position convention."
 }

 PointLocation {
  definition = "The problem of finding the face, cell or region containing a query point."
 }

 Arrangement {
  definition = "The subdivision induced by a collection of geometric objects such as lines, segments or curves."
 }

 RobustPredicate {
  definition = "A predicate evaluated reliably despite degeneracy or finite-precision arithmetic."
 }

 Complexity {
  definition = "The time, space, preprocessing, query and output-sensitive cost of a geometric algorithm."
 }
}

RELATIONS {
 ComputationalGeometryOntology --is_child_of--> ComputationalGeometry
 GeometricProblem --is_solved_by--> GeometricAlgorithm
 GeometricAlgorithm --uses--> GeometricPredicate
 GeometricAlgorithm --may_use--> GeometricDataStructure
 PointSet --is_input_to--> ConvexHull
 PointSet --is_input_to--> ClosestPair
 SegmentSet --is_input_to--> SegmentIntersection
 Polygon --is_input_to--> PolygonTriangulation
 Arrangement --supports--> PointLocation
 VoronoiDiagram --is_dual_to--> DelaunayTriangulation
 KDTree --supports--> RangeSearching
 Quadtree --supports--> SpatialDecomposition
 BSPTree --supports--> SpatialPartition
 RTree --supports--> SpatialIndexing
 OrientationPredicate --supports--> ConvexHull
 OrientationPredicate --supports--> SegmentIntersection
 IncirclePredicate --supports--> DelaunayTriangulation
 RobustPredicate --mitigates--> NumericalError
 GeneralPosition --simplifies--> GeometricCombinatorics
 Degeneracy --complicates--> GeometricAlgorithm
}

OPERATORS {
 ORIENTATION_2D(a,b,c) :=
  sign((b_x-a_x)*(c_y-a_y)-(b_y-a_y)*(c_x-a_x))

 INCIRCLE_2D(a,b,c,d) :=
  sign_of_oriented_incircle_determinant(a,b,c,d)

 SEGMENTS_INTERSECT(a,b,c,d) :=
  orientation_and_collinearity_logic(a,b,c,d)

 POINT_IN_POLYGON(p,P) :=
  winding_number_or_ray_crossing_test(p,P)

 CONVEX_HULL(S) :=
  minimum_convex_container_of_S

 CLOSEST_PAIR(S) :=
  argmin_{p!=q in S} distance(p,q)

 VORONOI(S) :=
  nearest_site_partition_of_space

 DELAUNAY(S) :=
  triangulation_dual_to_Voronoi

 TRIANGULATE(P) :=
  noncrossing_triangle_decomposition_of_polygon

 POINT_LOCATION(p,Subdivision) :=
  containing_region_or_boundary_classification

 RANGE_SEARCH(D,Q) :=
  report_objects_matching_geometric_query_Q

 COMPLEXITY(A,input_model) :=
  asymptotic_time_space_preprocessing_query_output_costs
}

DEFINITIONS {
 D1 = "Computational geometry combines geometry with algorithm design."
 D2 = "Geometric predicates determine combinatorial decisions."
 D3 = "Convex hulls summarise extremal point-set geometry."
 D4 = "Voronoi and Delaunay structures encode proximity."
 D5 = "Arrangements encode incidence and subdivision structure."
 D6 = "Point location converts spatial subdivisions into queryable structures."
 D7 = "Sweep-line algorithms exploit ordered event processing."
 D8 = "Robustness is necessary because finite-precision arithmetic can corrupt predicate signs."
 D9 = "Degeneracies must be handled explicitly or excluded by stated assumptions."
 D10 = "Algorithm complexity depends on dimension, input model and output requirements."
}

AXIOMS {
 A1_CORRECTNESS:
  A computational-geometry algorithm must produce geometrically valid output

 A2_PREDICATE_CONSISTENCY:
  Predicate outcomes must be logically and combinatorially consistent

 A3_COMPLEXITY:
  Algorithm analysis must state relevant time and space complexity

 A4_DEGENERACY:
  Degenerate configurations must be handled or explicitly excluded

 A5_HULL:
  Convex hull output is convex and contains all input points

 A6_TRIANGULATION:
  A valid triangulation partitions the intended domain without overlapping triangle interiors

 A7_VORONOI_DELAUNAY:
  Standard planar Voronoi and Delaunay structures are dual under compatible assumptions

 A8_ROBUSTNESS:
  Numeric implementation must preserve sign and incidence decisions sufficiently for topological consistency
}

REASONING {

 R1_PROBLEM_CLASSIFICATION {
  INPUT = problem_statement
  IDENTIFY = object_types
  IDENTIFY = dimension
  IDENTIFY = metric
  IDENTIFY = query_or_output
  CLASSIFY = hull_proximity_intersection_containment_triangulation_arrangement_location_visibility_search_or_motion
  RETURN = problem_class
 }

 R2_ALGORITHM_SELECTION {
  INPUT = [problem_class,input_size,dimension,query_pattern]
  SELECT = appropriate_algorithm_family
  ANALYSE = expected_complexity
  RETURN = algorithm_candidate
 }

 R3_PREDICATE_SELECTION {
  INPUT = local_geometric_decision
  IF turn_or_sidedness
   RETURN OrientationPredicate
  IF Delaunay_legality
   RETURN IncirclePredicate
  IF containment
   RETURN PointInPolygon_or_PointLocationPredicate
  IF intersection
   RETURN SegmentIntersectionPredicate
 }

 R4_CONVEX_HULL {
  INPUT = point_set
  SELECT = monotone_chain_Graham_scan_divide_and_conquer_incremental_or_dimension_specific_method
  COMPUTE = hull
  VERIFY = containment_convexity_and_vertex_order
  RETURN = hull
 }

 R5_PROXIMITY {
  INPUT = sites_or_points
  IF closest_pair_goal
   APPLY = divide_and_conquer_or_spatial_structure
  ELSE IF nearest_site_partition_goal
   APPLY = Voronoi
  ELSE IF triangulated_proximity_goal
   APPLY = Delaunay
  RETURN = proximity_result
 }

 R6_INTERSECTION {
  INPUT = geometric_objects
  IF small_fixed_number
   USE = direct_predicate_logic
  ELSE
   USE = sweep_line_arrangement_or_spatial_index
  RETURN = intersection_structure
 }

 R7_POINT_LOCATION {
  INPUT = subdivision_and_query_model
  PREPROCESS = suitable_search_structure
  QUERY = point
  RETURN = containing_face_edge_vertex_or_outside
 }

 R8_TRIANGULATION {
  INPUT = polygon_or_point_set
  DISTINGUISH = polygon_triangulation_vs_Delaunay_triangulation
  COMPUTE = selected_triangulation
  VERIFY = noncrossing_and_coverage_conditions
  RETURN = triangulation
 }

 R9_ROBUSTNESS {
  INPUT = numeric_predicate
  ESTIMATE = error_risk
  IF near_degenerate
   ESCALATE = adaptive_or_exact_arithmetic
  VERIFY = consistent_sign
  RETURN = robust_result
 }

 R10_COMPLEXITY {
  INPUT = algorithm_and_input_model
  COMPUTE = asymptotic_time
  COMPUTE = space
  INCLUDE = preprocessing_query_and_output_sensitive_terms_when_relevant
  RETURN = complexity_profile
 }
}

CONSTRAINTS {
 C1 = "Dimension must be tracked because many algorithms are dimension dependent."
 C2 = "Metric assumptions must be explicit for proximity structures."
 C3 = "General-position assumptions must never be silently imposed."
 C4 = "Degenerate cases can change combinatorial output."
 C5 = "Floating-point predicates near zero require robustness safeguards."
 C6 = "Worst-case, expected and output-sensitive complexities must not be conflated."
 C7 = "Static and dynamic query settings require different data-structure analysis."
 C8 = "Polygon triangulation and point-set Delaunay triangulation are distinct problems."
 C9 = "Spatial-index performance depends on workload and dimensionality."
 C10 = "Coordinate representation must preserve intended geometric semantics."
}

SEMANTIC_EQUIVALENCE {
 "ComputationalGeometryOntology" <=> "CoreAlgorithmicGeometryOntology"
 "GeometricPredicate" <=> "CombinatorialGeometryDecision"
 "ConvexHull" <=> "MinimumConvexContainer"
 "ClosestPair" <=> "MinimumDistancePair"
 "VoronoiDiagram" <=> "NearestSitePartition"
 "DelaunayTriangulation" <=> "VoronoiDualTriangulation"
 "RobustPredicate" <=> "PrecisionSafeGeometricDecision"
}

VALIDATION {
 V1 = "Problem dimension is identified."
 V2 = "Metric is identified when relevant."
 V3 = "Predicate outputs are sign-consistent."
 V4 = "Degeneracy policy is explicit."
 V5 = "Hull output is convex and contains inputs."
 V6 = "Triangulation output has no illegal overlaps."
 V7 = "Point-location output is consistent with subdivision topology."
 V8 = "Complexity statement matches the algorithm and model."
 V9 = "Robustness strategy matches numeric representation."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 COMPUTATIONAL_GEOMETRY_ONTOLOGY = 0.99
 PROBLEM_CLASSIFICATION = 0.99
 ALGORITHM_SELECTION = 0.98
 PREDICATE_REASONING = 0.99
 HULL_REASONING = 0.99
 PROXIMITY_REASONING = 0.99
 INTERSECTION_REASONING = 0.99
 ROBUSTNESS_REASONING = 0.99
 COMPLEXITY_REASONING = 0.98

 POLICY =
  "Reduce confidence when dimension, metric, degeneracy policy, numeric model, query workload, output sensitivity or algorithmic assumptions are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  ComputationalGeometryReasoning,
  GeometricProblemClassification,
  AlgorithmSelection,
  DataStructureSelection,
  ComplexityAnalysis,
  GeometricPredicateReasoning,
  ConvexHullReasoning,
  ProximityReasoning,
  IntersectionReasoning,
  TriangulationReasoning,
  ArrangementReasoning,
  PointLocationReasoning,
  SpatialSearchReasoning,
  RobustnessReasoning,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "computational geometry ontology" -> ComputationalGeometryOntology
  "computational geometry" -> ComputationalGeometryOntology WHEN ontology_context
  "geometric algorithm" -> GeometricAlgorithm
  "geometric data structure" -> GeometricDataStructure
  "geometric predicate" -> GeometricPredicate
  "convex hull" -> ConvexHull
  "closest pair" -> ClosestPair
  "Voronoi diagram" -> VoronoiDiagram
  "Delaunay triangulation" -> DelaunayTriangulation
  "point location" -> PointLocation
 }

 INTERPRETATION_ORDER = [
  detect_computational_geometry_ontology_context,
  identify geometric_objects_dimension_metric_and_input_model,
  identify problem_goal_and_query_pattern,
  identify degeneracy_precision_and_general_position assumptions,
  classify computational_geometry_problem,
  select algorithm_data_structure_and_predicates,
  analyse correctness_complexity_and_robustness,
  verify geometric_and_combinatorial invariants,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("computational geometry ontology")
  OR ontology_context_with_geometric_algorithms
  THEN activate(ComputationalGeometryOntology)

 E2:
  IF geometric_decision_requested
  THEN identify exact predicate before selecting higher-level algorithm

 E3:
  IF convex_hull_requested
  THEN choose algorithm according_to dimension_input_size_and_output requirements

 E4:
  IF proximity_requested
  THEN route to closest_pair_Voronoi_Delaunay_or_nearest_neighbour structure

 E5:
  IF many_intersections_requested
  THEN consider sweep_line_arrangement_or_spatial_index

 E6:
  IF point_location_requested
  THEN distinguish preprocessing_and_query phases

 E7:
  IF triangulation_requested
  THEN classify polygon_vs_point_set problem

 E8:
  IF numeric_near_degeneracy_detected
  THEN escalate to adaptive_or_exact predicate computation

 E9:
  IF complexity_requested
  THEN state time_space_preprocessing_query_and_output terms as applicable
}

RECURSION {
 ENTRY = ComputationalGeometryOntology

 EXPAND(ComputationalGeometryOntology) -> [
  GeometricProblem,
  GeometricAlgorithm,
  GeometricDataStructure,
  GeometricPredicate,
  ConvexHull,
  ClosestPair,
  SegmentIntersection,
  PointInPolygon,
  PointLocation,
  VoronoiDiagram,
  DelaunayTriangulation,
  PolygonTriangulation,
  Arrangement,
  SweepLineAlgorithm,
  RangeSearching,
  SpatialIndex,
  Visibility,
  MotionPlanning,
  RobustPredicate,
  Degeneracy,
  Complexity
 ]

 EXPAND(GeometricPredicate) -> [
  OrientationPredicate,
  IncirclePredicate,
  IntersectionPredicate,
  ContainmentPredicate
 ]

 EXPAND(SpatialIndex) -> [
  KDTree,
  Quadtree,
  BSPTree,
  RangeTree,
  RTree
 ]

 EXPAND(Proximity) -> [
  ClosestPair,
  NearestNeighbour,
  VoronoiDiagram,
  DelaunayTriangulation
 ]

 EXPAND(Robustness) -> [
  ExactArithmetic,
  AdaptivePrecision,
  SymbolicPerturbation,
  GeneralPosition,
  DegeneracyHandling
 ]

 STOP_CONDITION =
  "Stop when the geometric problem, algorithm, predicate, data structure, complexity profile, degeneracy treatment and correctness conditions are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Geometry"

 IMMEDIATE_CONTEXTS = [
  "Computational Geometry",
  "Geometry Ontology",
  "Coordinate Geometry Ontology",
  "Vector Geometry Ontology"
 ]

 RELATED_ONTOLOGIES = [
  "Computational Geometry",
  "Geometry Ontology",
  "Coordinate Geometry Ontology",
  "Analytic Geometry Ontology",
  "Vector Geometry Ontology",
  "Plane Geometry",
  "Solid Geometry",
  "Topology Ontology",
  "Linear Algebra Ontologies",
  "Algorithm Ontologies",
  "Data Structure Ontologies",
  "Computational Mathematics Ontologies"
 ]

 ROUTE_RULES = [
  "Computational Geometry Ontology -> Computational Geometry for parent algorithmic-geometry framework",
  "Computational Geometry Ontology -> Geometry for object semantics",
  "Computational Geometry Ontology -> Coordinate Geometry for coordinate predicates",
  "Computational Geometry Ontology -> Vector Geometry for orientation, projection and distance reasoning",
  "Computational Geometry Ontology -> Topology for subdivision and incidence consistency",
  "Computational Geometry Ontology -> Linear Algebra for determinant predicates",
  "Computational Geometry Ontology -> Algorithm Ontologies for design and complexity",
  "Computational Geometry Ontology -> Data Structure Ontologies for spatial indexing",
  "Computational Geometry Ontology -> Computational Mathematics for numerical robustness"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible algorithms, predicates, data structures, problem classes or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"

 RULES = [
  "Preserve geometric-problem classification semantics.",
  "Preserve predicate-first correctness reasoning.",
  "Preserve explicit degeneracy handling.",
  "Preserve dimension and metric awareness.",
  "Preserve algorithm complexity distinctions.",
  "Preserve robustness requirements.",
  "Preserve algorithm-versus-data-structure distinction.",
  "Preserve machine-readable computational-geometry semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "Computational geometry studies algorithms and data structures for geometric objects, spatial relations and geometric optimisation problems."

 PROBLEM_SUMMARY =
  "A geometric problem is classified by object type, dimension, metric, query model and desired output."

 PREDICATE_SUMMARY =
  "Orientation, incircle, intersection and containment predicates determine geometric combinatorics."

 HULL_SUMMARY =
  "The convex hull is the smallest convex set containing the input point set."

 PROXIMITY_SUMMARY =
  "Voronoi, Delaunay and closest-pair structures encode nearest-neighbour and proximity relationships."

 LOCATION_SUMMARY =
  "Point location identifies the subdivision cell containing a query point."

 COMPLEXITY_SUMMARY =
  "Computational geometry evaluates time, space, preprocessing, query and output-sensitive complexity."

 ROBUSTNESS_SUMMARY =
  "Degeneracy and finite-precision error require explicit robust-predicate handling."
}

FLOW {
 INPUT
 -> detect_computational_geometry_ontology_context
 -> identify objects_dimension_metric_input_size_query_model_and_output
 -> identify degeneracy_general_position_and_precision assumptions
 -> classify geometric_problem
 -> select geometric_predicates
 -> select algorithm_and_data_structure
 -> analyse correctness_complexity_and_robustness
 -> verify geometric_combinatorial_and_numeric constraints
 -> route to computational_geometry geometry coordinate vector topology linear_algebra algorithms data_structures_or_computational_mathematics ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Computational Geometry Ontology provides the core semantic model for algorithmic geometry. It classifies geometric problems and connects them to predicates, algorithms, spatial data structures, complexity analysis and robustness requirements across convex hulls, proximity, intersections, triangulations, arrangements, point location, visibility and spatial search."
}

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

}

END_FLOW