Delaunay Triangulation Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Delaunay Triangulation Ontology 2 within the Kireth Research Semantic Library. Delaunay triangulation connects sites into simplices such that, under standard Euclidean assumptions, no input site lies inside the circumcircle or circumsphere of any simplex. This ontology supports planar and higher-dimensional Delaunay structures, empty-circle predicates, Voronoi duality, incremental and divide-and-conquer algorithms, edge flips, constrained Delaunay triangulation, mesh generation, refinement, degeneracy handling, exact predicates, robustness, complexity, verification and reproducibility.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = DelaunayTriangulation
 ENTITY_CLASS = GeometricTriangulationFramework
 PRIMARY_CONTEXT = ComputationalGeometry
 DEFINITION = "A Delaunay triangulation is a triangulation of a point set in which the interior of the circumcircle of each triangle, or circumsphere of each simplex in higher dimensions, contains no input point under the chosen geometric assumptions."
 SYMBOLIC_FORMS = [
  "InCircle(a,b,c,d)<=0 for Delaunay triangle abc and external site d under orientation convention",
  "Delaunay(P) dual Voronoi(P)",
  "empty(circumcircle(T))",
  "edge_is_Delaunay iff local_empty_circle_condition"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for Delaunay simplices, empty-circle and empty-sphere predicates, Voronoi duality, local edge legality, construction, constrained variants, refinement, robustness and verification."
}

SCOPE {
 INCLUDE = [
  DelaunayTriangulation,DelaunayTessellation,DelaunayComplex,
  PointSet,Site,Vertex,DelaunayVertex,DelaunayEdge,
  DelaunayTriangle,DelaunayFace,DelaunaySimplex,
  Triangulation,SimplicialComplex,Simplex,Tetrahedron,
  Circumcircle,Circumsphere,Circumcenter,Circumradius,
  EmptyCircumcircleProperty,EmptyCircumsphereProperty,
  IncirclePredicate,InspherePredicate,OrientationPredicate,
  LocalDelaunayCondition,GlobalDelaunayCondition,
  EdgeFlip,DiagonalFlip,LegalEdge,IllegalEdge,
  LawsonFlipAlgorithm,FlipGraph,
  VoronoiDiagram,VoronoiCell,VoronoiEdge,VoronoiVertex,
  DelaunayVoronoiDuality,NearestNeighbourRelationship,
  IncrementalDelaunay,BowyerWatsonAlgorithm,
  RandomisedIncrementalDelaunay,DivideAndConquerDelaunay,
  SweepLineDelaunay,LiftingMap,ParaboloidLifting,
  ConvexHullRelationship,HigherDimensionalConvexHull,
  RegularTriangulation,WeightedDelaunayTriangulation,
  PowerDiagram,RegularSubdivision,
  ConstrainedDelaunayTriangulation,CDT,
  ConstrainedEdge,ConstraintSegment,VisibilityCriterion,
  ConformingDelaunayTriangulation,
  RestrictedDelaunayTriangulation,
  DelaunayRefinement,RuppertAlgorithm,ChewAlgorithm,
  MeshGeneration,MeshRefinement,QualityMesh,
  MinimumAngle,MaximumAngle,AspectRatio,
  SliverElement,SliverExudation,
  BoundaryRecovery,SteinerPoint,SteinerVertex,
  SegmentEncroachment,TriangleEncroachment,
  GeneralPosition,Degeneracy,Cocircularity,Cosphericality,
  Collinearity,Coplanarity,DuplicatePoint,
  SymbolicPerturbation,SimulationOfSimplicity,
  ExactPredicate,AdaptivePrecision,FloatingPointFilter,
  ExactArithmetic,NumericalRobustness,
  FloatingPointArithmetic,MachinePrecision,RoundOffError,
  DynamicDelaunay,KineticDelaunay,OnlineDelaunay,
  ParallelDelaunay,GPUDelaunay,DistributedDelaunay,
  PointLocation,WalkingPointLocation,
  ConflictRegion,ConflictCavity,CavityBoundary,
  SuperTriangle,SuperSimplex,GhostVertex,
  ComputationalComplexity,TimeComplexity,SpaceComplexity,
  ExpectedONLogN,OutputComplexity,
  NearestNeighbourGraph,EuclideanMinimumSpanningTree,
  GabrielGraph,RelativeNeighbourhoodGraph,
  NaturalNeighbourInterpolation,SibsonInterpolation,
  SurfaceReconstruction,AlphaComplex,AlphaShape,
  Verification,InvariantChecking,Benchmarking,
  ReferenceResult,Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  ArbitraryTriangulationWithoutEmptyCircleSemantics,
  VoronoiDiagramWithoutTriangulationConstruction,
  FiniteElementMeshWithoutDelaunayCriterion,
  PolygonTriangulationWithoutPointSetDelaunaySemantics
 ]
 DISAMBIGUATION_RULE = "When a point-set triangulation is defined by empty circumcircle or circumsphere conditions or by Voronoi duality, interpret the context as Delaunay triangulation."
}

CORE_CONCEPTS {
 DelaunayTriangulation = "Triangulation satisfying an empty-circle or empty-sphere criterion."
 EmptyCircumcircleProperty = "No input point lies strictly inside the circumcircle of a Delaunay triangle under general position."
 IncirclePredicate = "Predicate testing whether a point lies inside, on or outside a triangle's circumcircle."
 EdgeFlip = "Local operation replacing one diagonal of a convex quadrilateral with the other."
 BowyerWatsonAlgorithm = "Incremental Delaunay method that removes conflicted simplices and retriangulates the resulting cavity."
 DelaunayVoronoiDuality = "Dual relation connecting Delaunay simplices to Voronoi cells, edges and vertices."
 ConstrainedDelaunayTriangulation = "Delaunay-like triangulation preserving required constraint segments."
 DelaunayRefinement = "Mesh-improvement process inserting points to improve element quality while maintaining Delaunay structure."
}

RELATIONS {
 DelaunayTriangulation --is_child_of--> ComputationalGeometry
 DelaunayTriangulation --is_type_of--> Triangulation
 DelaunayTriangulation --is_dual_to--> VoronoiDiagram
 DelaunayEdge --corresponds_to--> VoronoiAdjacency
 DelaunayTriangle --corresponds_to--> VoronoiVertexIn2DGeneralPosition
 Circumcenter --corresponds_to--> VoronoiVertex
 IncirclePredicate --tests--> EmptyCircumcircleProperty
 InspherePredicate --tests--> EmptyCircumsphereProperty
 EdgeFlip --repairs--> LocalDelaunayViolation
 LawsonFlipAlgorithm --uses--> EdgeFlip
 BowyerWatsonAlgorithm --uses--> ConflictCavity
 ParaboloidLifting --relates--> DelaunayToLowerConvexHull
 WeightedDelaunayTriangulation --is_dual_to--> PowerDiagram
 DelaunayRefinement --improves--> MeshQuality
 EuclideanMinimumSpanningTree --is_subgraph_of--> DelaunayTriangulation
 GabrielGraph --is_subgraph_of--> DelaunayTriangulation
 Verification --checks--> DelaunayResult
}

OPERATORS {
 INCIRCLE(a,b,c,d) := sign_of_incircle_determinant_under_orientation_convention
 INSPHERE(a,b,c,d,e) := sign_of_insphere_determinant_under_orientation_convention
 DELAUNAY_EDGE_TEST(a,b,c,d) := local_empty_circle_condition_for_shared_edge_ab
 EDGE_FLIP(a,b,c,d) := replace_diagonal_ab_with_cd_when_illegal
 BOWYER_WATSON_INSERT(p,T) := remove_simplices_whose_circumcircles_contain_p_and_retriangulate_cavity
 DELAUNAY(P) := triangulation_satisfying_empty_sphere_property
 LIFT(p) := (p,||p||^2)
 LOWER_HULL(lift(P)) := dual_structure_for_Delaunay
}

AXIOMS {
 A1 = "A planar Delaunay triangulation satisfies the empty-circumcircle property."
 A2 = "In general position, the planar Delaunay triangulation is unique."
 A3 = "Cocircular or cospherical input can produce multiple valid Delaunay triangulations."
 A4 = "Voronoi adjacency is dual to Delaunay connectivity under standard assumptions."
 A5 = "Local edge legality characterises planar Delaunay triangulations for ordinary unconstrained cases."
 A6 = "Paraboloid lifting relates Delaunay triangulation to a lower convex hull."
 A7 = "Exact sign decisions for orientation and incircle predicates are crucial to combinatorial correctness."
 A8 = "Delaunay results require empty-circle, adjacency, robustness and reproducibility validation."
}

REASONING {
 R1_CONTEXT = identify(dimension,input_sites,constraints,weighting,mesh_quality_goal,degeneracy_risk,output_requirements)
 R2_PREPROCESS = remove_or_handle_duplicates_and_establish_coordinate_conventions
 R3_VARIANT = classify(ordinary,weighted,constrained,restricted,conforming_or_refined_Delaunay)
 R4_PREDICATES = configure(orientation,incircle,insphere,exact_or_adaptive_predicates)
 R5_ALGORITHM = choose(BowyerWatson,divide_and_conquer,sweep,edge_flip,lifting_or_higher_dimensional_method)
 R6_CONSTRUCT = generate_simplices_edges_faces_and_adjacency
 R7_CONSTRAINTS = if_constrained preserve_or_recover_required_segments_or_facets
 R8_REFINEMENT = if_quality_target insert_Steiner_points_and_retriangulate
 R9_COMPLEXITY = assess(input_size,dimension,output_size_and_algorithmic_cost)
 R10_VALIDATE = check_empty_circle_or_sphere_property,adjacency,duality,degeneracies_and_reproducibility
}

CONSTRAINTS {
 C1 = "Duplicate points must be removed or handled explicitly."
 C2 = "Cocircular or cospherical points can make the triangulation nonunique."
 C3 = "Floating-point incircle and orientation predicates can create invalid topology."
 C4 = "Constrained Delaunay triangulations do not satisfy the ordinary empty-circle condition across blocked visibility."
 C5 = "Higher-dimensional Delaunay complexes can have large combinatorial complexity."
 C6 = "Sliver simplices can occur in three-dimensional Delaunay meshes despite acceptable edge lengths."
 C7 = "Poor point-location strategies can dominate incremental construction cost."
 C8 = "Steiner-point insertion can increase mesh size substantially during refinement."
 C9 = "Randomised incremental methods require seed-aware reproducibility."
 C10 = "A visually plausible triangulation does not guarantee the Delaunay property."
}

SEMANTIC_EQUIVALENCE {
 "DelaunayTriangulation" <=> "DelaunayTessellation"
 "BowyerWatsonAlgorithm" <=> "Bowyer-Watson"
 "ConstrainedDelaunayTriangulation" <=> "CDT"
 "WeightedDelaunayTriangulation" <=> "RegularTriangulation"
 "DelaunayVoronoiDuality" <=> "VoronoiDelaunayDuality"
}

VALIDATION {
 V1 = "Dimension and input-site representation are explicit."
 V2 = "Duplicate-point policy is documented."
 V3 = "Constraint and weighting semantics are documented where used."
 V4 = "Orientation and incircle or insphere predicates are documented."
 V5 = "Precision and robustness model is documented."
 V6 = "Every simplex satisfies the appropriate local or global Delaunay condition."
 V7 = "Adjacency and simplex orientation are consistent."
 V8 = "Voronoi duality is checked where applicable."
 V9 = "Constrained edges or facets are preserved where required."
 V10 = "Results are reproducible under documented arithmetic, insertion order and random-seed settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 DELAUNAY_DEFINITION = 0.99
 INCIRCLE_REASONING = 0.99
 BOWYER_WATSON_REASONING = 0.99
 EDGE_FLIP_REASONING = 0.99
 VORONOI_DUALITY_REASONING = 0.99
 CONSTRAINED_DELAUNAY_REASONING = 0.98
 HIGHER_DIMENSIONAL_REASONING = 0.97
 POLICY = "Reduce confidence when dimension, duplicate policy, constraint semantics, predicate precision, degeneracy handling, insertion order or weighting are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,OntologyGrounding,DelaunayReasoning,
  EmptyCircumcircleReasoning,IncirclePredicateReasoning,
  InspherePredicateReasoning,EdgeFlipReasoning,
  BowyerWatsonReasoning,DivideAndConquerDelaunayReasoning,
  VoronoiDualityReasoning,WeightedDelaunayReasoning,
  ConstrainedDelaunayReasoning,DelaunayRefinementReasoning,
  MeshQualityReasoning,RobustPredicateReasoning,
  DegeneracyReasoning,ComplexityReasoning,
  VerificationReasoning,KnowledgeGraphConstruction,
  RetrievalAugmentation,RecursiveInference
 ]
 NORMALISE {
  "Delaunay triangulation" -> DelaunayTriangulation
  "Delaunay tessellation" -> DelaunayTriangulation
  "Bowyer-Watson" -> BowyerWatsonAlgorithm
  "CDT" -> ConstrainedDelaunayTriangulation
  "regular triangulation" -> WeightedDelaunayTriangulation
 }
}

EXECUTION_RULES {
 E1 = "If a triangulation is defined by empty-circle or empty-sphere semantics or Voronoi duality, activate DelaunayTriangulationOntology2."
 E2 = "Identify dimension, constraints, weighting and degeneracy policy before construction."
 E3 = "Use robust orientation and incircle or insphere predicates."
 E4 = "For planar unconstrained point sets, use Bowyer-Watson, divide-and-conquer, sweep, lifting or edge-flip construction as appropriate."
 E5 = "For constrained problems, preserve required edges or facets and use constrained-Delaunay legality semantics."
 E6 = "For mesh-quality goals, use Delaunay refinement with explicit angle or radius-edge criteria."
 E7 = "For higher dimensions, account explicitly for combinatorial output growth."
 E8 = "Validate local or global Delaunay conditions and Voronoi duality."
 E9 = "Document precision, insertion order and randomisation semantics for reproducibility."
}

RECURSION {
 ENTRY = DelaunayTriangulation
 EXPAND(DelaunayTriangulation) -> [
  DelaunayTessellation,DelaunayComplex,PointSet,Site,Vertex,
  DelaunayVertex,DelaunayEdge,DelaunayTriangle,DelaunayFace,
  DelaunaySimplex,Triangulation,SimplicialComplex,Simplex,
  Circumcircle,Circumsphere,Circumcenter,Circumradius,
  EmptyCircumcircleProperty,EmptyCircumsphereProperty,
  IncirclePredicate,InspherePredicate,OrientationPredicate,
  LocalDelaunayCondition,GlobalDelaunayCondition,EdgeFlip,
  LegalEdge,IllegalEdge,LawsonFlipAlgorithm,VoronoiDiagram,
  DelaunayVoronoiDuality,IncrementalDelaunay,BowyerWatsonAlgorithm,
  RandomisedIncrementalDelaunay,DivideAndConquerDelaunay,
  SweepLineDelaunay,LiftingMap,ParaboloidLifting,
  ConvexHullRelationship,RegularTriangulation,
  WeightedDelaunayTriangulation,PowerDiagram,
  ConstrainedDelaunayTriangulation,CDT,ConstrainedEdge,
  ConformingDelaunayTriangulation,RestrictedDelaunayTriangulation,
  DelaunayRefinement,RuppertAlgorithm,ChewAlgorithm,
  MeshGeneration,MeshRefinement,QualityMesh,MinimumAngle,
  AspectRatio,SliverElement,SteinerPoint,SegmentEncroachment,
  GeneralPosition,Degeneracy,Cocircularity,Cosphericality,
  DuplicatePoint,SymbolicPerturbation,ExactPredicate,
  AdaptivePrecision,FloatingPointFilter,NumericalRobustness,
  DynamicDelaunay,KineticDelaunay,ParallelDelaunay,
  PointLocation,ConflictRegion,ConflictCavity,CavityBoundary,
  SuperTriangle,ComputationalComplexity,NearestNeighbourGraph,
  EuclideanMinimumSpanningTree,GabrielGraph,
  NaturalNeighbourInterpolation,SurfaceReconstruction,
  AlphaComplex,AlphaShape,Verification,Benchmarking,
  ReferenceResult,Reproducibility
 ]
 EXPAND(DelaunayFamilies) -> [
  PlanarDelaunayTriangulations,
  HigherDimensionalDelaunayComplexes,
  WeightedAndRegularTriangulations,
  ConstrainedDelaunayTriangulations,
  DelaunayRefinementAndMeshGeneration,
  DynamicAndKineticDelaunay,
  ParallelDelaunayAlgorithms,
  RobustExactDelaunayComputation
 ]
 STOP_CONDITION = "Stop when dimension, predicates, algorithm, constraints, weighting, refinement, robustness, duality, complexity and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Geometry Ontology 2"
 RELATED_ONTOLOGIES = [
  "Computational Geometry Ontology 2",
  "Computational Geometry",
  "Voronoi Diagram Ontology 2",
  "Convex Hull Ontology 2",
  "Finite Element Method Ontology",
  "Mesh Generation Ontologies",
  "Nearest Neighbour Ontology",
  "Numerical Stability Ontology 2",
  "Floating Point Arithmetic Ontology",
  "Discrete Mathematics Ontologies",
  "Computational Topology Ontologies"
 ]
 ROUTE_RULES = [
  "Delaunay Triangulation -> Computational Geometry Ontology 2 for parent semantics",
  "Delaunay Triangulation -> Voronoi Diagram for geometric duality",
  "Delaunay Triangulation -> Convex Hull for paraboloid-lifting relationships",
  "Delaunay Triangulation -> Finite Element Method for mesh-generation applications",
  "Delaunay Triangulation -> Mesh Generation for refinement and quality criteria",
  "Delaunay Triangulation -> Nearest Neighbour for proximity graph relationships",
  "Delaunay Triangulation -> Numerical Stability for robust predicates",
  "Delaunay Triangulation -> Floating Point Arithmetic for precision-sensitive incircle and orientation tests",
  "Delaunay Triangulation -> Discrete Mathematics for triangulation combinatorics",
  "Delaunay Triangulation -> Computational Topology for simplicial-complex structure"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible Delaunay variants, refinement methods or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve Delaunay-versus-arbitrary-triangulation distinction.",
  "Preserve ordinary-versus-constrained Delaunay distinction.",
  "Preserve unweighted-versus-weighted triangulation distinction.",
  "Preserve local-edge-legality-versus-global-empty-circle distinction.",
  "Preserve Voronoi-versus-Delaunay distinction.",
  "Preserve exact-versus-approximate predicate distinction.",
  "Preserve triangulation-versus-refinement distinction.",
  "Preserve machine-readable Delaunay semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "A Delaunay triangulation is a point-set triangulation satisfying an empty circumcircle or circumsphere criterion."
 PREDICATE_SUMMARY = "Orientation and incircle or insphere predicates determine local Delaunay legality."
 DUALITY_SUMMARY = "Delaunay connectivity is dual to Voronoi adjacency under standard assumptions."
 ALGORITHM_SUMMARY = "Bowyer-Watson, edge-flip, divide-and-conquer, sweep and lifting methods construct Delaunay structures."
 CONSTRAINT_SUMMARY = "Constrained Delaunay triangulations preserve required segments while relaxing ordinary visibility across those constraints."
 REFINEMENT_SUMMARY = "Delaunay refinement inserts Steiner points to improve mesh quality according to declared geometric criteria."
 VALIDATION_SUMMARY = "Delaunay results should be checked for empty-circle or sphere legality, orientation, adjacency, constraint preservation, duality, robustness and reproducibility."
}

FLOW {
 INPUT
 -> detect_Delaunay_context
 -> identify_dimension_input_sites_constraints_weighting_mesh_quality_goal_degeneracy_risk_and_output_requirements
 -> preprocess_duplicates_and_define_coordinate_conventions
 -> classify_ordinary_weighted_constrained_restricted_conforming_or_refined_Delaunay_variant
 -> configure_orientation_incircle_insphere_exact_adaptive_or_filtered_predicates
 -> select_BowyerWatson_divide_and_conquer_sweep_edge_flip_lifting_or_higher_dimensional_algorithm
 -> construct_simplices_edges_faces_and_adjacency
 -> if_constrained_recover_required_edges_or_facets
 -> if_refinement_requested_insert_Steiner_points_and_retriangulate
 -> assess_input_dimension_output_and_algorithmic_complexity
 -> verify_empty_circle_or_sphere_conditions_orientation_adjacency_constraint_preservation_and_Voronoi_duality
 -> route_to_related_computational_geometry_Voronoi_convex_hull_FEM_mesh_generation_nearest_neighbour_stability_floating_point_discrete_mathematics_and_topology_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Delaunay Triangulation Ontology 2 defines point-set triangulations satisfying empty circumcircle or circumsphere conditions. It supports Delaunay vertices, edges, triangles and simplices, local edge legality, incircle and insphere predicates, Lawson edge flips, Bowyer-Watson incremental construction, divide-and-conquer, sweep and paraboloid-lifting methods, Voronoi duality, weighted and regular triangulations, constrained and conforming Delaunay structures, Delaunay refinement through Ruppert and Chew-style methods, mesh-quality criteria, Steiner points, dynamic and kinetic Delaunay, parallel construction, exact and adaptive predicates, degeneracy handling, complexity, verification, benchmarking and reproducibility."
}

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

}

END_FLOW