Delaunay Triangulation Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the mathematical ontology of Delaunay triangulations within the Kireth Research Semantic Library. A Delaunay triangulation is a triangulation of a finite point set in which the circumcircle of every triangle contains no input point in its interior, under the standard planar Euclidean formulation. It is dual to the Voronoi diagram and supports proximity reasoning, mesh generation, interpolation, nearest-neighbour structure, empty-circle predicates, edge flipping, incremental construction, divide-and-conquer methods, degeneracy handling and robust geometric computation.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = DelaunayTriangulation
 SYMBOLIC_FORMS = [
  "DT(S)",
  "Del(S)",
  "empty circumcircle triangulation"
 ]
 ENTITY_CLASS = ProximityTriangulation
 PRIMARY_CONTEXT = ComputationalGeometry
 DEFINITION = "A planar Delaunay triangulation of a finite point set is a triangulation in which the open circumcircle of every triangle contains no input point."
 SEMANTIC_ROLE = "Provides the canonical proximity-preserving triangulation framework dual to Voronoi diagrams and supports meshing, interpolation, nearest-neighbour relations and robust planar subdivision."
}

SCOPE {
 INCLUDE = [
  DelaunayTriangulation,
  DelaunayTriangle,
  DelaunayEdge,
  DelaunayVertex,
  Triangulation,
  PointSet,
  Circumcircle,
  Circumcenter,
  EmptyCircleProperty,
  LocalDelaunayCondition,
  IncirclePredicate,
  EdgeFlip,
  VoronoiDiagram,
  VoronoiDuality,
  NearestNeighbourGraph,
  RelativeNeighbourhoodGraphRelation,
  EuclideanMinimumSpanningTreeRelation,
  IncrementalDelaunay,
  BowyerWatsonAlgorithm,
  DivideAndConquerDelaunay,
  EdgeFlippingAlgorithm,
  Degeneracy,
  CocircularPoints,
  GeneralPosition,
  ConstrainedDelaunayTriangulation,
  HigherDimensionalDelaunay
 ]

 EXCLUDE_AS_PRIMARY = [
  ArbitraryTriangulationWithoutDelaunayCriterion,
  PolygonTriangulationUnlessDelaunayConstraintIsCentral,
  VoronoiDiagramExceptAsDualStructure,
  TetrahedralisationWithoutDelaunayContext
 ]

 DISAMBIGUATION_RULE =
  "When a triangulation is defined by an empty circumcircle condition, Voronoi duality, incircle tests or local Delaunay edge legality, interpret it as a Delaunay triangulation."
}

CORE_CONCEPTS {

 DelaunayTriangulation {
  definition = "A triangulation satisfying the empty-circumcircle property."
 }

 DelaunayTriangle {
  definition = "A triangle whose circumcircle contains no input site in its interior."
 }

 DelaunayEdge {
  definition = "An edge belonging to a Delaunay triangulation and dual to a Voronoi edge under standard planar assumptions."
 }

 Circumcircle {
  definition = "The unique circle through three noncollinear triangle vertices."
 }

 Circumcenter {
  definition = "The center of a triangle's circumcircle."
 }

 EmptyCircleProperty {
  definition = "No input point lies in the interior of the circumcircle of any Delaunay triangle."
 }

 LocalDelaunayCondition {
  definition = "An interior edge is locally Delaunay if the opposite vertex of each adjacent triangle does not lie inside the other's circumcircle."
 }

 IncirclePredicate {
  definition = "A determinant-based test deciding whether a query point lies inside, on or outside the circumcircle of an oriented triangle."
 }

 EdgeFlip {
  definition = "Replacement of one diagonal of a convex quadrilateral by the other."
 }

 VoronoiDuality {
  definition = "Delaunay vertices correspond to sites, Delaunay edges to shared Voronoi boundaries, and Delaunay triangles to Voronoi vertices under generic planar conditions."
 }
}

RELATIONS {
 DelaunayTriangulation --is_special_case_of--> Triangulation
 DelaunayTriangle --is_face_of--> DelaunayTriangulation
 DelaunayEdge --is_edge_of--> DelaunayTriangulation
 Circumcircle --belongs_to--> DelaunayTriangle
 DelaunayTriangle --satisfies--> EmptyCircleProperty
 DelaunayEdge --satisfies--> LocalDelaunayCondition
 DelaunayTriangulation --is_dual_to--> VoronoiDiagram
 VoronoiEdge --corresponds_to--> DelaunayEdge
 VoronoiVertex --corresponds_to--> DelaunayTriangle
 VoronoiCell --corresponds_to--> DelaunayVertex
 IncirclePredicate --tests--> LocalDelaunayCondition
 EdgeFlip --repairs--> NonDelaunayEdge
 BowyerWatsonAlgorithm --constructs--> DelaunayTriangulation
 DivideAndConquerDelaunay --constructs--> DelaunayTriangulation
}

OPERATORS {
 INCIRCLE(a,b,c,d) :=
  sign_of_oriented_incircle_determinant(a,b,c,d)

 IS_DELAUNAY_TRIANGLE(a,b,c,S) :=
  no_p_in_S_minus_{a,b,c} lies_strictly_inside_circumcircle(a,b,c)

 IS_LOCALLY_DELAUNAY(edge_ab,triangles_abc_abd) :=
  c_not_inside_circumcircle(a,b,d)
  AND d_not_inside_circumcircle(a,b,c)
  under consistent_orientation

 DELAUNAY_TRIANGULATION(S) :=
  triangulation_T_of_S
  such_that every_triangle_in_T satisfies_empty_circle_property

 FLIP_EDGE(ab,quadrilateral_acbd) :=
  replace_edge_ab_with_cd
  WHEN quadrilateral_is_convex

 VORONOI_DUAL_EDGE(p_i,p_j) :=
  edge(p_i,p_j)
  WHEN VoronoiCells(p_i,p_j) share_boundary_edge

 CIRCUMCENTER(a,b,c) :=
  intersection_of_perpendicular_bisectors(a,b,c)

 EMPTY_CIRCUMCIRCLE(a,b,c,S) :=
  for_all_p_in_S_minus_{a,b,c}
  p_not_in_interior_of_circumcircle(a,b,c)
}

DEFINITIONS {
 D1 = "A Delaunay triangulation is a triangulation with empty open circumcircles."
 D2 = "The Delaunay triangulation is dual to the Voronoi diagram under standard planar assumptions."
 D3 = "A generic planar point set has a unique Delaunay triangulation when no four sites are cocircular."
 D4 = "Cocircular sites may produce multiple valid Delaunay triangulations."
 D5 = "An illegal interior edge can be replaced by an edge flip."
 D6 = "The incircle predicate is central to Delaunay legality tests."
 D7 = "The convex hull forms the outer boundary of the planar Delaunay triangulation."
 D8 = "Delaunay triangulations tend to avoid skinny triangles in the max-min angle sense."
 D9 = "Every Euclidean minimum spanning tree edge belongs to the Delaunay triangulation."
 D10 = "Constrained Delaunay triangulations modify visibility and admissibility conditions."
}

AXIOMS {
 A1_TRIANGULATION:
  DelaunayTriangulation is a valid triangulation of the point set domain

 A2_EMPTY_CIRCLE:
  Every Delaunay triangle has an open circumcircle containing no input point

 A3_VORONOI_DUALITY:
  Under standard planar Euclidean assumptions, Delaunay adjacency corresponds to Voronoi-cell adjacency

 A4_LOCAL_GLOBAL:
  For planar triangulations in general position, all interior edges locally Delaunay implies the triangulation is Delaunay

 A5_EDGE_FLIP:
  A non-Delaunay interior edge in a convex quadrilateral can be flipped to improve local Delaunay legality

 A6_UNIQUENESS:
  If no four input points are cocircular and no degeneracies intervene, the planar Delaunay triangulation is unique

 A7_HULL_BOUNDARY:
  Convex-hull edges are Delaunay edges

 A8_PROXIMITY_SUPERGRAPH:
  The Delaunay graph contains important proximity graphs including the Euclidean minimum spanning tree
}

REASONING {

 R1_DELAUNAY_VALIDATION {
  INPUT = triangulation_T_and_point_set_S
  VERIFY = T_is_valid_triangulation
  FOR each_triangle
   TEST = empty_circumcircle
  IF all_pass
   RETURN Delaunay
  ELSE
   RETURN NonDelaunay
 }

 R2_LOCAL_EDGE_TEST {
  INPUT = interior_edge_with_two_adjacent_triangles
  VERIFY = convex_quadrilateral_when_flip_considered
  APPLY = incircle_predicate
  RETURN = LocallyDelaunayOrIllegal
 }

 R3_EDGE_FLIPPING {
  INPUT = triangulation
  WHILE illegal_edge_exists
   FLIP = illegal_edge
  RETURN = locally_Delaunay_triangulation
 }

 R4_BOWYER_WATSON {
  INPUT = point_set
  INITIALISE = supertriangle
  FOR each_point_p
   FIND = triangles_whose_circumcircles_contain_p
   REMOVE = bad_triangles
   EXTRACT = cavity_boundary
   RETRIANGULATE = cavity_with_p
  REMOVE = supertriangle_incident_faces
  RETURN = DelaunayTriangulation
 }

 R5_VORONOI_DUAL {
  INPUT = VoronoiDiagram
  FOR each_pair_of_cells_sharing_edge
   CONNECT = generating_sites
  RETURN = Delaunay_graph_or_triangulation
 }

 R6_CIRCUMCENTER_REASONING {
  INPUT = noncollinear_triangle
  COMPUTE = perpendicular_bisector_intersection
  RETURN = circumcenter_and_radius
 }

 R7_DEGENERACY {
  INPUT = point_set
  DETECT = duplicates_collinearities_cocircularities
  IF cocircular
   APPLY = triangulation_tie_policy
  RETURN = valid_Delaunay_structure_under_convention
 }

 R8_PROXIMITY {
  INPUT = DelaunayTriangulation
  DERIVE = candidate_nearest_neighbour_edges
  DERIVE = Euclidean_MST_supergraph_relation
  RETURN = proximity_structure
 }

 R9_CONSTRAINED_DELAUNAY {
  INPUT = points_and_constraint_segments
  PRESERVE = constraints
  APPLY = visibility_based_empty_circle_or_local_legality condition
  RETURN = constrained_Delaunay_triangulation
 }
}

CONSTRAINTS {
 C1 = "Standard empty-circle statements assume Euclidean point-site geometry unless otherwise specified."
 C2 = "Cocircular points can destroy uniqueness."
 C3 = "Collinear point sets may not admit a two-dimensional triangulation."
 C4 = "Incircle sign depends on triangle orientation convention."
 C5 = "Floating-point incircle error can corrupt triangulation topology."
 C6 = "Edge flips require a suitable convex quadrilateral."
 C7 = "Constrained Delaunay triangulation is not identical to unconstrained Delaunay triangulation."
 C8 = "Voronoi duality must match the same metric and weighting model."
 C9 = "Higher-dimensional Delaunay structures use simplices and circumspheres rather than planar triangles and circumcircles."
}

SEMANTIC_EQUIVALENCE {
 "DelaunayTriangulation" <=> "EmptyCircumcircleTriangulation"
 "DelaunayEdge" <=> "VoronoiAdjacencyEdge" WHEN standard_planar_context
 "DelaunayTriangle" <=> "VoronoiVertexDualFace" WHEN generic_planar_context
 "LocalDelaunayCondition" <=> "LegalEdgeCondition"
 "IncirclePredicate" <=> "CircumcircleMembershipPredicate"
}

VALIDATION {
 V1 = "Triangulation covers the convex hull without overlapping triangle interiors."
 V2 = "Every triangle satisfies the empty open circumcircle condition."
 V3 = "Incircle tests use consistent orientation."
 V4 = "Voronoi-Delaunay adjacency is consistent."
 V5 = "Hull boundary edges are preserved."
 V6 = "Cocircular degeneracy follows declared tie policy."
 V7 = "Constrained edges remain present in constrained variants."
 V8 = "Robust predicates maintain combinatorial consistency."
 V9 = "Higher-dimensional generalisations use correct simplex structure."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 DELAUNAY_DEFINITION = 0.99
 EMPTY_CIRCLE_REASONING = 0.99
 LOCAL_EDGE_REASONING = 0.99
 VORONOI_DUALITY_REASONING = 0.99
 BOWYER_WATSON_REASONING = 0.99
 DEGENERACY_REASONING = 0.99
 CONSTRAINED_DELAUNAY_REASONING = 0.98
 ROBUSTNESS_REASONING = 0.99

 POLICY =
  "Reduce confidence when metric, orientation, cocircularity policy, dimensionality, constraint segments or numerical precision assumptions are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  DelaunayReasoning,
  ComputationalGeometryReasoning,
  TriangulationReasoning,
  VoronoiDualityReasoning,
  IncirclePredicateReasoning,
  EdgeFlipReasoning,
  MeshGenerationReasoning,
  ProximityReasoning,
  DegeneracyReasoning,
  RobustPredicateReasoning,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "Delaunay triangulation" -> DelaunayTriangulation
  "Delaunay triangle" -> DelaunayTriangle
  "Delaunay edge" -> DelaunayEdge
  "empty circumcircle" -> EmptyCircleProperty
  "incircle test" -> IncirclePredicate
  "edge flip" -> EdgeFlip
  "Bowyer-Watson" -> BowyerWatsonAlgorithm
  "constrained Delaunay triangulation" -> ConstrainedDelaunayTriangulation
 }

 INTERPRETATION_ORDER = [
  detect_Delaunay_context,
  identify point_set_dimension_metric_constraints_and_orientation,
  identify validation_construction_duality_edge_legality_or_proximity goal,
  detect degeneracy_and_numeric_precision assumptions,
  apply empty_circle_incircle_edge_flip_or_dual reasoning,
  verify triangulation_duality_and_robustness constraints,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("Delaunay triangulation")
  OR empty_circumcircle_triangulation_context
  THEN activate(DelaunayTriangulationOntology)

 E2:
  IF triangle_legality_requested
  THEN use empty_circumcircle_or_incircle test

 E3:
  IF interior_edge_legality_requested
  THEN test local_Delaunay_condition

 E4:
  IF illegal_edge_detected
  AND quadrilateral_convex
  THEN permit edge_flip

 E5:
  IF construction_requested
  THEN select Bowyer_Watson_divide_and_conquer_edge_flipping_or_Voronoi_dual method

 E6:
  IF Voronoi_diagram_available
  THEN derive Delaunay adjacency from shared Voronoi boundaries

 E7:
  IF cocircular_points_detected
  THEN apply explicit nonuniqueness_or_tie convention

 E8:
  IF constrained_segments_present
  THEN use constrained_Delaunay semantics

 E9:
  IF numerical_near_degeneracy_detected
  THEN use robust_or_adaptive incircle predicates
}

RECURSION {
 ENTRY = DelaunayTriangulation

 EXPAND(DelaunayTriangulation) -> [
  DelaunayTriangle,
  DelaunayEdge,
  DelaunayVertex,
  Circumcircle,
  Circumcenter,
  EmptyCircleProperty,
  LocalDelaunayCondition,
  IncirclePredicate,
  EdgeFlip,
  VoronoiDuality,
  IncrementalDelaunay,
  BowyerWatsonAlgorithm,
  DivideAndConquerDelaunay,
  ConstrainedDelaunayTriangulation,
  HigherDimensionalDelaunay,
  Degeneracy
 ]

 EXPAND(VoronoiDuality) -> [
  VoronoiCell,
  VoronoiEdge,
  VoronoiVertex,
  DelaunayEdge,
  DelaunayTriangle
 ]

 EXPAND(ConstructionAlgorithm) -> [
  BowyerWatsonAlgorithm,
  DivideAndConquerDelaunay,
  EdgeFlippingAlgorithm,
  IncrementalDelaunay
 ]

 EXPAND(Degeneracy) -> [
  DuplicatePoint,
  CollinearPoints,
  CocircularPoints,
  SymbolicPerturbation,
  TieBreakingPolicy
 ]

 STOP_CONDITION =
  "Stop when the Delaunay triangulation, triangle legality, edge legality, circumcircle, Voronoi dual, construction, constrained variant, proximity relation or degeneracy handling is sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Geometry"

 IMMEDIATE_CONTEXTS = [
  "Computational Geometry Ontology",
  "Voronoi Diagram Ontology",
  "Convex Hull Ontology",
  "Triangulation Ontologies"
 ]

 RELATED_ONTOLOGIES = [
  "Computational Geometry",
  "Computational Geometry Ontology",
  "Voronoi Diagram Ontology",
  "Convex Hull Ontology",
  "Coordinate Geometry Ontology",
  "Vector Geometry Ontology",
  "Polygon Ontology",
  "Mesh Generation Ontologies",
  "Linear Algebra Ontologies",
  "Algorithm Ontologies"
 ]

 ROUTE_RULES = [
  "Delaunay Triangulation -> Computational Geometry Ontology for parent algorithmic semantics",
  "Delaunay Triangulation -> Voronoi Diagram for geometric duality",
  "Delaunay Triangulation -> Convex Hull for outer-boundary and lifting relations",
  "Delaunay Triangulation -> Coordinate Geometry for circumcircle equations",
  "Delaunay Triangulation -> Vector Geometry and Linear Algebra for determinant predicates",
  "Delaunay Triangulation -> Mesh Generation for triangulated-domain quality",
  "Delaunay Triangulation -> Algorithm Ontologies for construction and complexity"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible Delaunay variants, algorithms, dimensions or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"

 RULES = [
  "Preserve empty-circumcircle semantics.",
  "Preserve Voronoi duality under compatible assumptions.",
  "Preserve local edge-legality semantics.",
  "Preserve cocircular nonuniqueness handling.",
  "Preserve constrained-versus-unconstrained distinction.",
  "Preserve orientation-aware incircle testing.",
  "Preserve numerical robustness requirements.",
  "Preserve machine-readable Delaunay semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "A planar Delaunay triangulation is a triangulation in which no input point lies inside the open circumcircle of any triangle."

 EMPTY_CIRCLE_SUMMARY =
  "Every Delaunay triangle satisfies the empty open circumcircle property."

 DUALITY_SUMMARY =
  "Delaunay adjacency is dual to shared Voronoi-cell boundaries under standard planar Euclidean assumptions."

 LOCAL_EDGE_SUMMARY =
  "An interior edge is locally Delaunay when the opposite vertices do not violate the incircle condition."

 UNIQUENESS_SUMMARY =
  "The planar Delaunay triangulation is unique when the point set is in general position with no four cocircular sites."

 HULL_SUMMARY =
  "Convex-hull edges occur on the boundary of the Delaunay triangulation."

 ALGORITHM_SUMMARY =
  "Common construction methods include Bowyer-Watson, divide-and-conquer and edge flipping."

 ROBUSTNESS_SUMMARY =
  "Reliable Delaunay construction requires robust orientation and incircle predicates and explicit cocircular tie handling."
}

FLOW {
 INPUT
 -> detect_Delaunay_context
 -> identify point_set_dimension_metric_orientation_constraints_and_output_goal
 -> identify collinearity_cocircularity_and_numeric_precision assumptions
 -> select empty_circle_incircle_edge_flip_BowyerWatson_divide_and_conquer_or_Voronoi_dual pathway
 -> compute triangulation_legality_duality_or_proximity result
 -> verify coverage_nonoverlap_empty_circle_hull_boundary_and_robustness constraints
 -> route to computational_geometry Voronoi convex_hull coordinate vector linear_algebra mesh_generation_or_algorithm ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Delaunay Triangulation Ontology defines proximity-preserving triangulations through the empty-circumcircle criterion. It supports Delaunay triangles and edges, incircle predicates, local edge legality, edge flipping, Bowyer-Watson and divide-and-conquer construction, Voronoi duality, constrained variants, higher-dimensional generalisations, proximity-graph relations and robust degeneracy handling."
}

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

}

END_FLOW