Convex Hull Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Convex Hull Ontology 2 within the Kireth Research Semantic Library. A convex hull is the smallest convex set containing a given collection of points or geometric objects. This ontology supports two- and higher-dimensional convex hulls, extreme points, supporting hyperplanes, half-space representations, polygonal and polyhedral hulls, incremental, divide-and-conquer, Graham scan, monotone chain, gift-wrapping and QuickHull algorithms, degeneracy handling, robust orientation predicates, output-sensitive complexity, verification and reproducibility.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = ConvexHull
 ENTITY_CLASS = ConvexGeometricConstructionFramework
 PRIMARY_CONTEXT = ComputationalGeometry
 DEFINITION = "The convex hull of a set is the smallest convex set containing every point in that set."
 SYMBOLIC_FORMS = [
  "conv(P)=intersection of all convex sets containing P",
  "conv(P)={sum_i lambda_i p_i | lambda_i>=0, sum_i lambda_i=1}",
  "Hull(P)=boundary(conv(P)) in polygonal or polyhedral contexts"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for convex combinations, extreme points, supporting hyperplanes, hull construction algorithms, complexity, degeneracy, robustness and verification."
}

SCOPE {
 INCLUDE = [
  ConvexHull,ConvexSet,ConvexCombination,AffineCombination,
  PointSet,FinitePointSet,ExtremePoint,ExtremeVertex,
  HullVertex,HullEdge,HullFace,Facet,Ridge,
  ConvexPolygon,ConvexPolytope,ConvexPolyhedron,
  SupportingLine,SupportingPlane,SupportingHyperplane,
  HalfPlane,HalfSpace,Hyperplane,FaceLattice,
  VertexRepresentation,VRepresentation,
  HalfSpaceRepresentation,HRepresentation,
  ConvexHullBoundary,InteriorPoint,BoundaryPoint,
  CoplanarPoint,CollinearPoint,DuplicatePoint,
  GeneralPosition,Degeneracy,NearDegeneracy,
  OrientationPredicate,LeftTurn,RightTurn,CollinearityTest,
  DeterminantPredicate,ExactPredicate,AdaptivePrecision,
  FloatingPointFilter,SymbolicPerturbation,
  GrahamScan,GiftWrapping,JarvisMarch,MonotoneChain,
  AndrewMonotoneChain,QuickHull,IncrementalHull,
  DivideAndConquerHull,ChanAlgorithm,OutputSensitiveHull,
  RandomisedIncrementalHull,UpperHull,LowerHull,
  HullMerge,BridgeFinding,TangentFinding,
  SortingByPolarAngle,LexicographicSort,
  ClosestSupportingLine,VisibleFace,HorizonEdge,
  ConflictGraph,ConflictList,
  TwoDimensionalConvexHull,ThreeDimensionalConvexHull,
  HigherDimensionalConvexHull,DConvexHull,
  SimplicialPolytope,NonSimplicialPolytope,
  PolytopeTriangulation,FacetEnumeration,
  ExtremePointEnumeration,VertexEnumeration,
  HalfSpaceIntersection,Duality,PointHyperplaneDuality,
  PolarDual,ConvexDuality,
  CaratheodoryTheorem,HellyTheorem,RadonTheorem,
  SupportingHyperplaneTheorem,SeparationTheorem,
  MinkowskiSum,ConvexMinkowskiSum,
  Width,Diameter,RotatingCalipers,
  MinimumBoundingRectangle,MinimumAreaRectangle,
  MinimumEnclosingPolygon,SmallestEnclosingCircleRelationship,
  CollisionDetection,BoundingVolume,ConvexDecomposition,
  LinearProgrammingRelationship,FeasiblePolytope,
  ComputationalComplexity,TimeComplexity,SpaceComplexity,
  OutputSize,HullSize,OutputSensitiveComplexity,
  ONSquared,OLogN,ONLogN,ONH,
  DynamicConvexHull,OnlineConvexHull,
  KineticConvexHull,StreamingConvexHull,
  ApproximateConvexHull,EpsilonKernel,Coreset,
  ParallelConvexHull,GPUConvexHull,DistributedConvexHull,
  NumericalRobustness,FloatingPointArithmetic,
  MachinePrecision,RoundOffError,Conditioning,
  Verification,InvariantChecking,ReferenceResult,
  Benchmarking,Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  ConcaveHull,
  AlphaShapeWithoutConvexHullSemantics,
  GeneralPolygonBoundaryWithoutConvexity,
  ConvexOptimisationWithoutGeometricHullConstruction
 ]
 DISAMBIGUATION_RULE = "When the task is to construct or reason about the smallest convex set containing a point set, interpret the context as convex hull."
}

CORE_CONCEPTS {
 ConvexHull = "Smallest convex set containing a given point set."
 ExtremePoint = "Point in a convex set that cannot be expressed as a nontrivial convex combination of other points in the set."
 SupportingHyperplane = "Hyperplane touching a convex set while leaving the set entirely in one closed half-space."
 HullVertex = "Input or derived point appearing as a vertex of the convex hull."
 Facet = "Maximal proper face of a convex polytope."
 VRepresentation = "Representation of a convex polytope by its vertices."
 HRepresentation = "Representation of a convex polytope by linear inequalities or half-spaces."
 OutputSensitiveHull = "Hull algorithm whose runtime depends on both input size and hull output size."
}

RELATIONS {
 ConvexHull --is_child_of--> ComputationalGeometry
 ConvexHull --contains--> PointSet
 ConvexHull --is--> ConvexSet
 HullVertex --is_type_of--> ExtremePoint
 SupportingHyperplane --defines--> HullFace
 HullFace --belongs_to--> ConvexHullBoundary
 ConvexPolygon --is_2D_form_of--> ConvexHull
 ConvexPolytope --is_higher_dimensional_form_of--> ConvexHull
 GrahamScan --constructs--> TwoDimensionalConvexHull
 GiftWrapping --constructs--> ConvexHull
 MonotoneChain --constructs--> TwoDimensionalConvexHull
 QuickHull --constructs--> ConvexHull
 IncrementalHull --constructs--> ConvexHull
 ChanAlgorithm --is--> OutputSensitiveHull
 OrientationPredicate --supports--> HullConstruction
 HalfSpaceIntersection --is_dual_related_to--> ConvexHull
 MinkowskiSum --of_convex_sets_preserves--> Convexity
 RotatingCalipers --uses--> ConvexPolygon
 Verification --checks--> ConvexHullResult
}

OPERATORS {
 CONVEX_COMBINATION(P,lambda) := sum_i lambda_i*p_i with lambda_i>=0 and sum_i lambda_i=1
 CONVEX_HULL(P) := set_of_all_convex_combinations_of_P
 ORIENTATION(a,b,c) := sign((b_x-a_x)*(c_y-a_y)-(b_y-a_y)*(c_x-a_x))
 SUPPORTING_HALFSPACE(H,C) := halfspace_containing_C_with_boundary_touching_C
 HULL_VERTEX_TEST(p,P) := p_is_not_convex_combination_of_P_without_p
 UPPER_LOWER_HULL(P) := monotone_chain_decomposition(P)
 OUTPUT_SIZE(H) := number_of_hull_vertices_or_facets
}

AXIOMS {
 A1 = "The convex hull of a set is unique."
 A2 = "Every finite point set has a convex hull."
 A3 = "A finite two-dimensional hull is a convex polygon unless the points are degenerate to lower dimension."
 A4 = "Hull vertices are extreme points of the convex hull."
 A5 = "Supporting hyperplanes characterise faces of a convex polytope."
 A6 = "Interior input points do not appear as hull vertices."
 A7 = "Degenerate configurations require explicit collinearity or coplanarity handling."
 A8 = "Convex-hull results require geometric, combinatorial, robustness and complexity validation."
}

REASONING {
 R1_CONTEXT = identify(dimension,input_size,coordinate_precision,general_position_assumptions,degeneracy_risk,output_needs)
 R2_PREPROCESS = remove_or_handle_duplicates_and_normalise_representation
 R3_PREDICATES = select(orientation,visibility,supporting_plane_or_determinant_tests)
 R4_ALGORITHM = choose(GrahamScan,GiftWrapping,MonotoneChain,QuickHull,Incremental,DivideAndConquer,Chan_or_higher_dimensional_method)
 R5_ROBUSTNESS = apply(exact_predicates,adaptive_precision,filters_or_symbolic_perturbation)
 R6_CONSTRUCT = build_hull_vertices_edges_faces_and_adjacency
 R7_COMPLEXITY = assess(input_size,output_size,dimension_and_algorithmic_cost)
 R8_VERIFY = check(convexity,containment,orientation,extremality_and_face_consistency)
 R9_DERIVE = optionally_compute(width,diameter,bounding_rectangle_or_dual_structure)
 R10_REPRODUCE = document(ordering,precision,predicate_policy_and_random_seed_if_used)
}

CONSTRAINTS {
 C1 = "Duplicate points can cause unnecessary or inconsistent hull events if not handled."
 C2 = "Collinear or coplanar points require a documented policy for retaining or discarding boundary points."
 C3 = "Floating-point orientation predicates can fail near degeneracy."
 C4 = "Polar-angle sorting requires deterministic tie handling."
 C5 = "QuickHull can degrade on adversarial input."
 C6 = "Higher-dimensional hull complexity can grow rapidly with dimension."
 C7 = "Output size can dominate runtime for high-dimensional hulls."
 C8 = "Approximate hulls trade exact containment detail for reduced complexity."
 C9 = "Randomised incremental algorithms require seed-aware reproducibility."
 C10 = "A visually plausible hull is not sufficient evidence of combinatorial correctness."
}

SEMANTIC_EQUIVALENCE {
 "ConvexHull" <=> "ConvexEnvelope"
 "GiftWrapping" <=> "JarvisMarch"
 "MonotoneChain" <=> "AndrewMonotoneChain"
 "VertexRepresentation" <=> "VRepresentation"
 "HalfSpaceRepresentation" <=> "HRepresentation"
 "OutputSensitiveHull" <=> "OutputSensitiveConvexHullAlgorithm"
}

VALIDATION {
 V1 = "Input dimension and coordinate system are explicit."
 V2 = "Duplicate-point policy is documented."
 V3 = "Collinear or coplanar boundary-point policy is documented."
 V4 = "Orientation or supporting-hyperplane predicates are documented."
 V5 = "Precision and robustness model is documented."
 V6 = "Every input point lies inside or on the returned hull."
 V7 = "Hull vertices are extreme under the declared representation."
 V8 = "Hull orientation and face adjacency are consistent."
 V9 = "Complexity expectations are documented where relevant."
 V10 = "Results are reproducible under documented ordering, arithmetic and random-seed settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 CONVEX_HULL_DEFINITION = 0.99
 EXTREME_POINT_REASONING = 0.99
 GRAHAM_SCAN_REASONING = 0.99
 MONOTONE_CHAIN_REASONING = 0.99
 QUICKHULL_REASONING = 0.98
 HIGHER_DIMENSIONAL_REASONING = 0.98
 ROBUSTNESS_REASONING = 0.99
 POLICY = "Reduce confidence when dimension, boundary-point policy, degeneracy handling, predicate precision, output representation or algorithmic assumptions are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,OntologyGrounding,ConvexHullReasoning,
  ConvexSetReasoning,ExtremePointReasoning,
  SupportingHyperplaneReasoning,GrahamScanReasoning,
  GiftWrappingReasoning,MonotoneChainReasoning,
  QuickHullReasoning,IncrementalHullReasoning,
  OutputSensitiveHullReasoning,HigherDimensionalHullReasoning,
  HalfSpaceIntersectionReasoning,ConvexDualityReasoning,
  RotatingCalipersReasoning,RobustPredicateReasoning,
  DegeneracyReasoning,ComplexityReasoning,
  VerificationReasoning,KnowledgeGraphConstruction,
  RetrievalAugmentation,RecursiveInference
 ]
 NORMALISE {
  "convex hull" -> ConvexHull
  "convex envelope" -> ConvexHull
  "Jarvis march" -> GiftWrapping
  "Andrew monotone chain" -> MonotoneChain
  "V-representation" -> VRepresentation
  "H-representation" -> HRepresentation
 }
}

EXECUTION_RULES {
 E1 = "If the task seeks the smallest convex set containing input points, activate ConvexHullOntology2."
 E2 = "Identify input dimension and degeneracy policy before selecting an algorithm."
 E3 = "Use robust orientation or supporting-hyperplane predicates."
 E4 = "In two dimensions, choose Graham scan, monotone chain, gift wrapping, QuickHull or another appropriate method."
 E5 = "For output-sensitive requirements, consider algorithms whose complexity depends on hull size."
 E6 = "For higher dimensions, explicitly account for facet complexity and combinatorial growth."
 E7 = "Handle collinear, coplanar and duplicate points according to a declared policy."
 E8 = "Verify containment, convexity, extremality and orientation after construction."
 E9 = "Document precision, ordering and randomisation semantics for reproducibility."
}

RECURSION {
 ENTRY = ConvexHull
 EXPAND(ConvexHull) -> [
  ConvexSet,ConvexCombination,PointSet,ExtremePoint,HullVertex,
  HullEdge,HullFace,Facet,Ridge,ConvexPolygon,ConvexPolytope,
  SupportingLine,SupportingPlane,SupportingHyperplane,
  HalfPlane,HalfSpace,FaceLattice,VRepresentation,HRepresentation,
  InteriorPoint,BoundaryPoint,CollinearPoint,CoplanarPoint,
  DuplicatePoint,GeneralPosition,Degeneracy,OrientationPredicate,
  DeterminantPredicate,ExactPredicate,AdaptivePrecision,
  FloatingPointFilter,SymbolicPerturbation,GrahamScan,
  GiftWrapping,JarvisMarch,MonotoneChain,AndrewMonotoneChain,
  QuickHull,IncrementalHull,DivideAndConquerHull,ChanAlgorithm,
  OutputSensitiveHull,RandomisedIncrementalHull,UpperHull,
  LowerHull,HullMerge,TangentFinding,SortingByPolarAngle,
  VisibleFace,HorizonEdge,ConflictGraph,TwoDimensionalConvexHull,
  ThreeDimensionalConvexHull,HigherDimensionalConvexHull,
  SimplicialPolytope,FacetEnumeration,ExtremePointEnumeration,
  HalfSpaceIntersection,PointHyperplaneDuality,PolarDual,
  CaratheodoryTheorem,HellyTheorem,RadonTheorem,
  SupportingHyperplaneTheorem,SeparationTheorem,MinkowskiSum,
  Width,Diameter,RotatingCalipers,MinimumBoundingRectangle,
  EuclideanMinimumSpanningTree,DynamicConvexHull,
  KineticConvexHull,ApproximateConvexHull,EpsilonKernel,
  ParallelConvexHull,GPUConvexHull,NumericalRobustness,
  FloatingPointArithmetic,AlgorithmicComplexity,
  OutputSensitiveComplexity,Verification,Benchmarking,
  ReferenceResult,Reproducibility
 ]
 EXPAND(ConvexHullFamilies) -> [
  TwoDimensionalConvexHullAlgorithms,
  ThreeDimensionalConvexHullAlgorithms,
  HigherDimensionalConvexHullAlgorithms,
  OutputSensitiveConvexHullAlgorithms,
  DynamicAndKineticConvexHulls,
  ApproximateConvexHulls,
  RobustConvexHullComputation
 ]
 STOP_CONDITION = "Stop when dimension, predicates, algorithm, boundary policy, robustness, hull representation, complexity and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Geometry Ontology 2"
 RELATED_ONTOLOGIES = [
  "Computational Geometry Ontology 2",
  "Computational Geometry",
  "Geometry Ontologies",
  "Coordinate Geometry Ontologies",
  "Linear Programming Solver Ontology",
  "Optimisation Computation",
  "Numerical Linear Algebra Ontology 2",
  "Numerical Stability Ontology 2",
  "Floating Point Arithmetic Ontology",
  "Discrete Mathematics Ontologies",
  "Computational Topology Ontologies"
 ]
 ROUTE_RULES = [
  "Convex Hull -> Computational Geometry Ontology 2 for parent semantics",
  "Convex Hull -> Geometry Ontologies for convexity and geometric entities",
  "Convex Hull -> Coordinate Geometry for coordinate predicates",
  "Convex Hull -> Linear Programming for separation and half-space relationships",
  "Convex Hull -> Optimisation Computation for geometric optimisation",
  "Convex Hull -> Numerical Stability for robust predicates",
  "Convex Hull -> Floating Point Arithmetic for precision-sensitive orientation tests",
  "Convex Hull -> Discrete Mathematics for combinatorial face structure",
  "Convex Hull -> Computational Topology for polyhedral boundary structure"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible hull algorithms, representations or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve convex-set-versus-boundary distinction.",
  "Preserve extreme-point-versus-interior-point distinction.",
  "Preserve V-representation-versus-H-representation distinction.",
  "Preserve exact-versus-approximate hull distinction.",
  "Preserve input-size-versus-output-size complexity distinction.",
  "Preserve two-dimensional-versus-higher-dimensional distinction.",
  "Preserve predicate-versus-construction distinction.",
  "Preserve machine-readable convex-hull semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "The convex hull of a point set is the smallest convex set containing every input point."
 GEOMETRIC_SUMMARY = "Hull vertices are extreme points and hull faces lie on supporting hyperplanes."
 ALGORITHM_SUMMARY = "Graham scan, gift wrapping, monotone chain, QuickHull, incremental, divide-and-conquer and Chan-style methods construct hulls under different complexity trade-offs."
 REPRESENTATION_SUMMARY = "Convex polytopes can be represented by vertices and faces or by supporting half-spaces."
 ROBUSTNESS_SUMMARY = "Exact or adaptive predicates are important near collinear, coplanar or otherwise degenerate configurations."
 COMPLEXITY_SUMMARY = "Convex-hull complexity depends on input size, output size and dimension."
 VALIDATION_SUMMARY = "Hull results should be checked for containment, convexity, extremality, orientation, face consistency, robustness and reproducibility."
}

FLOW {
 INPUT
 -> detect_convex_hull_context
 -> identify_dimension_input_points_precision_degeneracy_risk_boundary_point_policy_and_output_requirements
 -> preprocess_duplicates_and_normalise_representation
 -> select_orientation_or_supporting_hyperplane_predicates
 -> choose_Graham_GiftWrapping_MonotoneChain_QuickHull_incremental_divide_and_conquer_Chan_or_higher_dimensional_algorithm
 -> configure_exact_adaptive_filtered_or_symbolic_robustness
 -> construct_hull_vertices_edges_faces_and_adjacency
 -> assess_input_output_dimension_and_algorithmic_complexity
 -> verify_all_points_contained_convexity_extremality_orientation_and_face_consistency
 -> optionally_derive_width_diameter_bounding_rectangle_halfspace_or_dual_structures
 -> route_to_related_computational_geometry_geometry_coordinate_geometry_linear_programming_optimisation_stability_floating_point_discrete_mathematics_and_topology_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Convex Hull Ontology 2 defines the smallest convex set containing a geometric point set. It supports convex combinations, extreme points, supporting lines, planes and hyperplanes, convex polygons and polytopes, V- and H-representations, Graham scan, gift wrapping, monotone chain, QuickHull, incremental, divide-and-conquer and output-sensitive algorithms, two- through higher-dimensional hulls, half-space intersection and duality relationships, rotating-calipers geometry, dynamic and kinetic hulls, approximate hulls and epsilon kernels, exact and adaptive predicates, degeneracy handling, algorithmic complexity, verification, benchmarking and reproducibility."
}

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

}

END_FLOW