Convex Hull Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the mathematical ontology of convex hulls within the Kireth Research Semantic Library. The convex hull of a set is the smallest convex set containing it. In computational geometry, convex hulls provide a fundamental boundary representation for point sets and support geometric algorithms, extremal reasoning, orientation predicates, half-space representations, support functions, polytopes, divide-and-conquer methods and complexity analysis. This ontology supports planar and higher-dimensional convex hulls, hull vertices, facets, edges, supporting hyperplanes, convex combinations, algorithms, degeneracies and relationships with computational geometry, linear algebra and optimisation.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = ConvexHull
 SYMBOLIC_FORMS = [
  "conv(S)",
  "CH(S)",
  "Conv(S)"
 ]
 ENTITY_CLASS = ConvexGeometricConstruction
 PRIMARY_CONTEXT = ComputationalGeometry
 DEFINITION = "The convex hull of a set S is the smallest convex set containing S, equivalently the set of all finite convex combinations of points of S."
 SEMANTIC_ROLE = "Provides the minimal convex enclosure framework for point sets, supporting boundary extraction, extremal reasoning, geometric optimisation, polytope construction and algorithmic geometry."
}

SCOPE {
 INCLUDE = [
  ConvexHull,
  ConvexSet,
  ConvexCombination,
  ExtremePoint,
  HullVertex,
  HullEdge,
  HullFacet,
  SupportingLine,
  SupportingHyperplane,
  HalfSpace,
  Polytope,
  ConvexPolygon,
  ConvexPolyhedron,
  PlanarConvexHull,
  HigherDimensionalConvexHull,
  OrientationPredicate,
  GrahamScan,
  JarvisMarch,
  MonotoneChain,
  QuickHull,
  DivideAndConquerHull,
  IncrementalHull,
  GiftWrapping,
  OutputSensitiveHull,
  Degeneracy,
  Collinearity,
  Coplanarity,
  Complexity
 ]

 EXCLUDE_AS_PRIMARY = [
  GeneralBoundingBox,
  ConcaveHullUnlessExplicit,
  AlphaShapeUnlessExplicit,
  ConvexOptimisationWithoutHullStructure
 ]

 DISAMBIGUATION_RULE =
  "When the goal is to find the smallest convex set containing input points, extract the outer convex boundary, identify extreme points or construct a convex polytope from data, interpret the context as a convex hull problem."
}

CORE_CONCEPTS {

 ConvexHull {
  definition = "The intersection of all convex sets containing S, equivalently all finite convex combinations of points of S."
 }

 ConvexSet {
  definition = "A set containing every line segment between any two of its points."
 }

 ConvexCombination {
  definition = "A weighted sum sum_i lambda_i p_i with lambda_i>=0 and sum_i lambda_i=1."
 }

 ExtremePoint {
  definition = "A point of a convex set that cannot be expressed as a nontrivial convex combination of two distinct points in the set."
 }

 HullVertex {
  definition = "An extreme input point appearing as a vertex of a finite point-set hull."
 }

 HullEdge {
  definition = "A one-dimensional face of a convex hull."
 }

 HullFacet {
  definition = "A maximal proper face of dimension one less than the hull."
 }

 SupportingHyperplane {
  definition = "A hyperplane touching a convex set while the set lies entirely in one closed half-space."
 }

 Polytope {
  definition = "The convex hull of finitely many points, equivalently a bounded intersection of finitely many half-spaces."
 }

 PlanarConvexHull {
  definition = "The convex polygon enclosing a finite planar point set."
 }
}

RELATIONS {
 ConvexHull --is_smallest_convex_superset_of--> Set
 ConvexHull --is_intersection_of--> ConvexSupersets
 ConvexHull --contains--> InputSet
 ConvexHull --consists_of--> ConvexCombinations
 HullVertex --is--> ExtremePoint
 HullEdge --is_face_of--> ConvexHull
 HullFacet --is_face_of--> ConvexHull
 SupportingHyperplane --supports--> ConvexHull
 SupportingHyperplane --defines--> HalfSpace
 FinitePointSet --has_convex_hull--> Polytope
 PlanarPointSet --has_convex_hull--> ConvexPolygon
 ConvexHullAlgorithm --computes--> ConvexHull
 OrientationPredicate --supports--> PlanarConvexHullAlgorithm
}

OPERATORS {
 CONVEX_HULL(S) :=
  intersection_of_all_convex_sets_containing_S

 CONVEX_COMBINATION(points,lambdas) :=
  sum_i lambda_i*points_i
  WHEN all_lambda_i>=0 AND sum_i lambda_i=1

 IS_CONVEX(C) :=
  for_all_x_y_in_C for_all_t_in_[0,1]
  t*x+(1-t)*y in C

 IS_EXTREME_POINT(p,C) :=
  no_distinct_x_y_in_C_and_t_in_(0,1)
  such_that p=t*x+(1-t)*y

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

 SUPPORT_FUNCTION(C,u) :=
  sup_{x_in_C} <u,x>

 SUPPORTING_HYPERPLANE(C,u) :=
  {x : <u,x>=h_C(u)}

 POINT_IN_HULL(q,S) :=
  q expressible_as_convex_combination_of_points_in_S

 PLANAR_HULL(S) :=
  ordered_extreme_points_forming_outer_convex_polygon
}

DEFINITIONS {
 D1 = "The convex hull is convex."
 D2 = "The convex hull contains the original set."
 D3 = "Every convex set containing S also contains conv(S)."
 D4 = "For finite S, conv(S) is a polytope."
 D5 = "Hull vertices are extreme points."
 D6 = "Interior input points do not appear as hull vertices."
 D7 = "Collinear boundary points may or may not be retained depending on output convention."
 D8 = "Supporting hyperplanes characterise faces of convex hulls."
 D9 = "Planar hull algorithms commonly rely on orientation tests."
 D10 = "The hull is invariant under permutations of the input set."
}

AXIOMS {
 A1_MINIMALITY:
  conv(S) is the smallest convex set containing S

 A2_CONVEX_COMBINATION:
  conv(S) equals the set of all finite convex combinations of points from S

 A3_IDEMPOTENCE:
  conv(conv(S))=conv(S)

 A4_MONOTONICITY:
  If A subset B then conv(A) subset conv(B)

 A5_AFFINE_EQUIVARIANCE:
  For affine map F, F(conv(S))=conv(F(S))

 A6_FINITE_POLYTOPE:
  Convex hull of a finite point set is a polytope

 A7_EXTREME_BOUNDARY:
  Finite hull vertices are extreme points of conv(S)

 A8_SUPPORTING_FACE:
  Every proper face of a polytope can be exposed by a supporting hyperplane under standard finite-dimensional convex geometry
}

REASONING {

 R1_HULL_CONSTRUCTION {
  INPUT = point_set_S
  IDENTIFY = dimension
  IDENTIFY = degeneracies
  SELECT = dimension_appropriate_hull_algorithm
  COMPUTE = boundary_representation
  VERIFY = convexity_and_containment
  RETURN = convex_hull
 }

 R2_PLANAR_MONOTONE_CHAIN {
  INPUT = planar_points
  SORT = lexicographically
  BUILD = lower_hull_using_orientation
  BUILD = upper_hull_using_orientation
  CONCATENATE = without_duplicate_endpoints
  RETURN = ordered_hull_vertices
 }

 R3_GRAHAM_SCAN {
  INPUT = planar_points
  SELECT = pivot
  SORT = by_polar_angle
  SCAN = orientation_stack
  RETURN = hull_vertices
 }

 R4_JARVIS_MARCH {
  INPUT = planar_points
  START = extreme_point
  REPEATEDLY_SELECT = next_most_counterclockwise_point
  STOP = return_to_start
  RETURN = hull
 }

 R5_POINT_IN_HULL {
  INPUT = [q,S]
  IF low_dimension_and_hull_known
   TEST = point_in_convex_polygon_or_polytope
  ELSE
   SOLVE = convex_combination_feasibility
  RETURN = InsideBoundaryOrOutside
 }

 R6_EXTREME_POINT {
  INPUT = [p,S]
  TEST = whether p_lies_in_conv(S\{p})
  IF false
   RETURN ExtremePoint
  ELSE
   RETURN NonExtreme
 }

 R7_SUPPORTING_FACE {
  INPUT = [hull,direction_u]
  COMPUTE = support_value
  COLLECT = points_attaining_maximum
  RETURN = exposed_face
 }

 R8_HIGHER_DIMENSION {
  INPUT = finite_points_in_Rd
  SELECT = incremental_divide_and_conquer_QuickHull_or_other_d_dimensional_method
  COMPUTE = face_lattice_or_boundary_facets
  VERIFY = supporting_hyperplane_conditions
  RETURN = polytope_hull
 }

 R9_DEGENERACY {
  INPUT = point_set
  DETECT = duplicates_collinearities_coplanarities
  APPLY = chosen_boundary_point_policy_and_robust_predicates
  RETURN = convention_consistent_hull
 }
}

CONSTRAINTS {
 C1 = "Dimension must be identified before selecting algorithms or face representations."
 C2 = "Duplicate points should not create duplicate hull vertices."
 C3 = "Collinear and coplanar boundary points require an explicit retention convention."
 C4 = "Floating-point orientation errors can corrupt hull topology."
 C5 = "A hull algorithm may return vertices only, edges/facets, or a full face lattice; output specification matters."
 C6 = "Worst-case complexity depends on dimension and output size."
 C7 = "Interior points must not be classified as extreme points."
 C8 = "Affine transformations preserve hull structure, but projective transformations do not generally preserve convexity."
 C9 = "Concave hulls and alpha shapes are different constructions."
}

SEMANTIC_EQUIVALENCE {
 "ConvexHull" <=> "MinimumConvexContainer"
 "ConvexHull" <=> "SetOfAllConvexCombinations"
 "HullVertex" <=> "ExtremeVertexOfFiniteHull"
 "SupportingHyperplane" <=> "HyperplaneDefiningSupportingHalfSpace"
 "PlanarConvexHull" <=> "OuterConvexPolygonOfPointSet"
 "Polytope" <=> "ConvexHullOfFinitePointSet"
}

VALIDATION {
 V1 = "All input points lie in the computed hull."
 V2 = "Output hull is convex."
 V3 = "Every reported hull vertex is extreme under the adopted boundary convention."
 V4 = "Planar hull vertex order is consistently clockwise or counterclockwise."
 V5 = "Hull has no self-intersections."
 V6 = "Supporting facets satisfy one-sided half-space containment."
 V7 = "Degenerate cases follow declared policy."
 V8 = "Algorithm complexity statement matches dimension and algorithm."
 V9 = "Robust predicates preserve combinatorial consistency."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 CONVEX_HULL_DEFINITION = 0.99
 PLANAR_HULL_REASONING = 0.99
 EXTREME_POINT_REASONING = 0.99
 SUPPORTING_FACE_REASONING = 0.98
 HIGHER_DIMENSIONAL_REASONING = 0.98
 DEGENERACY_REASONING = 0.99
 COMPLEXITY_REASONING = 0.98

 POLICY =
  "Reduce confidence when dimension, collinearity policy, numeric precision, output representation, general-position assumptions or higher-dimensional facet conventions are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  ConvexHullReasoning,
  ComputationalGeometryReasoning,
  ConvexityReasoning,
  ExtremePointReasoning,
  SupportingHyperplaneReasoning,
  PolytopeReasoning,
  AlgorithmSelection,
  ComplexityReasoning,
  RobustPredicateReasoning,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "convex hull" -> ConvexHull
  "convex envelope" -> ConvexHull
  "convex closure" -> ConvexHull
  "hull vertex" -> HullVertex
  "extreme point" -> ExtremePoint
  "supporting hyperplane" -> SupportingHyperplane
  "Graham scan" -> GrahamScan
  "Jarvis march" -> JarvisMarch
  "gift wrapping" -> JarvisMarch
  "monotone chain" -> MonotoneChain
  "QuickHull" -> QuickHull
 }

 INTERPRETATION_ORDER = [
  detect_convex_hull_context,
  identify point_set_dimension_and_metric_space,
  identify desired_output_vertices_edges_facets_or_membership,
  identify degeneracy_and_boundary_point_policy,
  select geometric_predicates_and_hull_algorithm,
  compute hull_or_related_extreme_structure,
  verify convexity_containment_extremality_and_robustness,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("convex hull")
  OR query_mentions("convex envelope")
  THEN activate(ConvexHullOntology)

 E2:
  IF planar_finite_point_set
  THEN permit monotone_chain_Graham_scan_Jarvis_or_QuickHull reasoning

 E3:
  IF orientation_predicate_required
  THEN use robust_signed_area_test

 E4:
  IF point_membership_in_hull_requested
  THEN use convex_polygon_polytope_or_convex_combination feasibility method

 E5:
  IF extreme_point_requested
  THEN test whether point lies in hull_of_remaining_points

 E6:
  IF higher_dimension
  THEN route to polytope_and_supporting_hyperplane reasoning

 E7:
  IF degeneracies_present
  THEN apply explicit collinear_coplanar_duplicate policy

 E8:
  IF algorithm_comparison_requested
  THEN compare time_space_output_sensitivity_and_robustness
}

RECURSION {
 ENTRY = ConvexHull

 EXPAND(ConvexHull) -> [
  ConvexSet,
  ConvexCombination,
  ExtremePoint,
  HullVertex,
  HullEdge,
  HullFacet,
  SupportingLine,
  SupportingHyperplane,
  HalfSpace,
  Polytope,
  ConvexPolygon,
  ConvexPolyhedron,
  PlanarConvexHull,
  HigherDimensionalConvexHull,
  ConvexHullAlgorithm,
  Degeneracy
 ]

 EXPAND(ConvexHullAlgorithm) -> [
  GrahamScan,
  JarvisMarch,
  MonotoneChain,
  QuickHull,
  DivideAndConquerHull,
  IncrementalHull,
  OutputSensitiveHull
 ]

 EXPAND(SupportStructure) -> [
  SupportFunction,
  SupportingHyperplane,
  ExposedFace,
  Facet,
  HalfSpaceRepresentation
 ]

 EXPAND(Degeneracy) -> [
  DuplicatePoint,
  CollinearPoints,
  CoplanarPoints,
  RobustOrientationPredicate,
  BoundaryRetentionPolicy
 ]

 STOP_CONDITION =
  "Stop when the convex hull, hull boundary, extreme points, supporting faces, containment status, algorithm choice, complexity or degeneracy handling is sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Geometry"

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

 RELATED_ONTOLOGIES = [
  "Computational Geometry",
  "Computational Geometry Ontology",
  "Geometry Ontology",
  "Coordinate Geometry Ontology",
  "Vector Geometry Ontology",
  "Polygon Ontology",
  "Polyhedron Ontology",
  "Linear Algebra Ontologies",
  "Optimisation Ontologies",
  "Algorithm Ontologies"
 ]

 ROUTE_RULES = [
  "Convex Hull -> Computational Geometry Ontology for parent algorithmic semantics",
  "Convex Hull -> Coordinate Geometry for point coordinates and orientation",
  "Convex Hull -> Vector Geometry for half-space and support reasoning",
  "Convex Hull -> Polygon for planar hull boundaries",
  "Convex Hull -> Polyhedron and Polytope for higher-dimensional hulls",
  "Convex Hull -> Linear Algebra for determinants and convex-combination systems",
  "Convex Hull -> Optimisation for support functions and feasibility",
  "Convex Hull -> Algorithm Ontologies for complexity and implementation"
 ]
}

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 smallest-convex-superset semantics.",
  "Preserve convex-combination equivalence.",
  "Preserve extreme-point semantics.",
  "Preserve affine equivariance.",
  "Preserve dimension awareness.",
  "Preserve degeneracy and numeric-robustness requirements.",
  "Preserve algorithm-versus-output-representation distinction.",
  "Preserve machine-readable convex-hull semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "The convex hull of S is the smallest convex set containing S, equivalently the set of all finite convex combinations of points of S."

 MINIMALITY_SUMMARY =
  "conv(S) is contained in every convex set that contains S."

 COMBINATION_SUMMARY =
  "conv(S)={sum_i lambda_i p_i : lambda_i>=0, sum_i lambda_i=1}."

 EXTREME_SUMMARY =
  "Hull vertices of a finite point set are extreme points."

 PLANAR_SUMMARY =
  "The planar convex hull is the outer convex polygon of the input point set."

 SUPPORT_SUMMARY =
  "Supporting lines or hyperplanes expose boundary faces of the hull."

 ALGORITHM_SUMMARY =
  "Planar convex hulls can be computed using algorithms such as monotone chain, Graham scan, Jarvis march or QuickHull."

 ROBUSTNESS_SUMMARY =
  "Reliable hull construction requires explicit handling of duplicates, collinearities and finite-precision orientation predicates."
}

FLOW {
 INPUT
 -> detect_convex_hull_context
 -> identify input_set_dimension_coordinate_representation_and_output_goal
 -> identify degeneracy_collinearity_coplanarity_and_boundary_policy
 -> choose robust_orientation_or_supporting predicates
 -> select hull_algorithm_or_convex_combination method
 -> compute hull_vertices_edges_facets_membership_or_support structure
 -> verify convexity_containment_extremality_order_and_robustness
 -> route to computational_geometry coordinate vector polygon polytope linear_algebra optimisation_or_algorithm ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Convex Hull Ontology defines the minimal convex enclosure of a point set and connects geometric convexity with algorithmic construction. It supports convex combinations, extreme points, hull vertices, edges and facets, supporting hyperplanes, polytopes, planar and higher-dimensional hull algorithms, point-in-hull reasoning, degeneracy handling and computational complexity."
}

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

}

END_FLOW