Voronoi Diagram Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Voronoi Diagram Ontology 2 within the Kireth Research Semantic Library. A Voronoi diagram partitions space into regions associated with sites according to a distance rule, with each region containing points closer to its generating site than to competing sites. This ontology supports Euclidean and weighted Voronoi diagrams, Voronoi cells, vertices and edges, bisectors, nearest-site partitions, Delaunay duality, construction algorithms, higher-dimensional generalisations, degeneracy handling, exact predicates, spatial queries, geometric optimisation, verification and reproducibility.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = VoronoiDiagram
 ENTITY_CLASS = NearestSiteSpacePartitionFramework
 PRIMARY_CONTEXT = ComputationalGeometry
 DEFINITION = "A Voronoi diagram partitions a metric space into cells such that each cell consists of points whose nearest generating site is a particular site under the chosen distance measure."
 SYMBOLIC_FORMS = [
  "V_i={x | d(x,p_i)<=d(x,p_j) for all j}",
  "Vor(P)=union_i V_i",
  "VoronoiEdge = locus of points equidistant to two sites",
  "VoronoiVertex = point equidistant to three or more sites in 2D general position"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for nearest-site partitions, Voronoi cells, bisectors, adjacency, Delaunay duality, construction algorithms, weighted variants, degeneracy, robustness and verification."
}

SCOPE {
 INCLUDE = [
  VoronoiDiagram,VoronoiTessellation,VoronoiPartition,
  Site,Generator,SeedPoint,PointSite,LineSite,SegmentSite,
  VoronoiCell,VoronoiRegion,VoronoiEdge,VoronoiVertex,
  VoronoiFace,VoronoiRidge,VoronoiFacet,
  Bisector,PerpendicularBisector,EquidistanceLocus,
  NearestSite,NearestNeighbour,NearestSitePartition,
  EuclideanDistance,MetricDistance,DistanceFunction,
  L1Voronoi,L2Voronoi,LInfinityVoronoi,
  WeightedVoronoiDiagram,AdditivelyWeightedVoronoi,
  MultiplicativelyWeightedVoronoi,PowerDiagram,
  LaguerreDiagram,ApolloniusDiagram,
  AnisotropicVoronoi,GeodesicVoronoi,
  RestrictedVoronoiDiagram,ClippedVoronoiDiagram,
  BoundedVoronoiCell,UnboundedVoronoiCell,
  OrdinaryVoronoiDiagram,OrderKVoronoiDiagram,
  FarthestPointVoronoiDiagram,
  HigherOrderVoronoi,NearestKSiteRegion,
  DelaunayTriangulation,DelaunayEdge,DelaunayTriangle,
  DelaunayDuality,EmptyCircumcircleProperty,
  Circumcenter,Circumcircle,Circumsphere,
  GeneralPosition,Degeneracy,Cocircularity,Cosphericality,
  Collinearity,DuplicateSite,NearDegeneracy,
  FortuneAlgorithm,FortuneSweep,SweepLine,
  BeachLine,ParabolicArc,SiteEvent,CircleEvent,
  EventQueue,SweepStatusStructure,
  IncrementalVoronoi,RandomisedIncrementalVoronoi,
  DivideAndConquerVoronoi,HalfPlaneIntersection,
  VoronoiFromDelaunay,DelaunayFromVoronoi,
  HigherDimensionalVoronoi,VoronoiPolyhedron,
  VoronoiPolytope,VoronoiComplex,
  CentroidalVoronoiTessellation,CVT,LloydAlgorithm,
  LloydRelaxation,GeneratorRelocation,
  DirichletTessellation,ThiessenPolygon,
  MedialAxisRelationship,SkeletonRelationship,
  NearestNeighbourSearch,PointLocation,
  SpatialIndex,KDTree,DelaunayLocation,
  FacilityLocation,ServiceArea,InfluenceRegion,
  CoverageProblem,Quantisation,VectorQuantisation,
  MeshGeneration,DelaunayRefinement,
  NaturalNeighbourInterpolation,SibsonInterpolation,
  VoronoiInterpolation,ScatteredDataInterpolation,
  ComputationalComplexity,TimeComplexity,SpaceComplexity,
  OLogN,ONLogN,OutputSize,
  ExactPredicate,OrientationPredicate,IncirclePredicate,
  AdaptivePrecision,FloatingPointFilter,SymbolicPerturbation,
  SimulationOfSimplicity,NumericalRobustness,
  FloatingPointArithmetic,MachinePrecision,RoundOffError,
  ParallelVoronoi,GPUVoronoi,DistributedVoronoi,
  DynamicVoronoi,KineticVoronoi,
  Verification,InvariantChecking,Benchmarking,
  ReferenceResult,Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  DelaunayTriangulationWithoutNearestSitePartitionSemantics,
  NearestNeighbourQueryWithoutVoronoiStructure,
  GeneralSpacePartitionWithoutDistanceBasedSiteAssignment,
  TessellationWithoutNearestSiteSemantics
 ]
 DISAMBIGUATION_RULE = "When space is partitioned into regions according to which site is nearest under a specified metric or weighted distance, interpret the context as a Voronoi diagram."
}

CORE_CONCEPTS {
 VoronoiDiagram = "Partition of space into nearest-site regions."
 VoronoiCell = "Region associated with one generating site."
 VoronoiEdge = "Boundary locus shared by neighbouring cells."
 VoronoiVertex = "Intersection of Voronoi edges or higher-order equidistance locus."
 Bisector = "Set of points equidistant from two sites."
 DelaunayDuality = "Dual relation linking Voronoi adjacency to Delaunay connectivity."
 PowerDiagram = "Weighted Voronoi structure induced by power distance."
 CentroidalVoronoiTessellation = "Voronoi diagram whose generators coincide with the centroids of their cells."
}

RELATIONS {
 VoronoiDiagram --is_child_of--> ComputationalGeometry
 VoronoiDiagram --partitions--> Space
 VoronoiDiagram --contains--> VoronoiCell
 VoronoiCell --is_generated_by--> Site
 VoronoiEdge --separates--> VoronoiCells
 VoronoiVertex --is_incident_to--> VoronoiEdges
 Bisector --defines_part_of--> VoronoiBoundary
 VoronoiDiagram --is_dual_to--> DelaunayTriangulation
 DelaunayEdge --corresponds_to--> VoronoiAdjacency
 DelaunayTriangle --corresponds_to--> VoronoiVertexIn2DGeneralPosition
 Circumcenter --corresponds_to--> VoronoiVertex
 EmptyCircumcircleProperty --supports--> DelaunayDuality
 FortuneAlgorithm --constructs--> PlanarVoronoiDiagram
 LloydAlgorithm --iteratively_updates--> CentroidalVoronoiTessellation
 PowerDiagram --is_type_of--> WeightedVoronoiDiagram
 Verification --checks--> VoronoiResult
}

OPERATORS {
 VORONOI_CELL(p_i,P,d) := {x | d(x,p_i)<=d(x,p_j) for all p_j in P}
 VORONOI_DIAGRAM(P,d) := union_i VORONOI_CELL(p_i,P,d)
 BISECTOR(p_i,p_j,d) := {x | d(x,p_i)=d(x,p_j)}
 POWER_DISTANCE(x,p_i,w_i) := ||x-p_i||^2-w_i
 POWER_CELL(p_i,w_i) := {x | power_i(x)<=power_j(x) for all j}
 DUAL_EDGE(p_i,p_j) := edge_if_Voronoi_cells_share_boundary
 CELL_CENTROID(V_i,rho) := integral_V_i x*rho(x) dx / integral_V_i rho(x) dx
 LLOYD_UPDATE(p_i) := centroid(V_i)
}

AXIOMS {
 A1 = "Every point in a Voronoi cell is no farther from its generating site than from competing sites under the chosen distance rule."
 A2 = "Voronoi boundaries are subsets of pairwise or higher-order equidistance loci."
 A3 = "In Euclidean two-dimensional general position, Voronoi vertices correspond to circumcentres of Delaunay triangles."
 A4 = "Voronoi adjacency and Delaunay connectivity are dual under standard assumptions."
 A5 = "Unbounded Voronoi cells correspond to sites on the convex hull in the ordinary planar Euclidean case."
 A6 = "Weighted distance definitions alter cell geometry and adjacency."
 A7 = "Degenerate configurations require explicit handling of cocircular, duplicate or otherwise non-general-position sites."
 A8 = "Voronoi results require metric, adjacency, robustness and duality validation."
}

REASONING {
 R1_CONTEXT = identify(dimension,site_type,distance_metric,weighting,bounding_domain,degeneracy_risk,output_requirements)
 R2_NORMALISE = remove_or_handle_duplicate_sites_and_define_metric_conventions
 R3_VARIANT = classify(ordinary,weighted,power,order_k,farthest,restricted,geodesic_or_centroidal_Voronoi)
 R4_ALGORITHM = choose(Fortune,incremental,divide_and_conquer,Delaunay_dual_or_higher_dimensional_method)
 R5_ROBUSTNESS = configure(orientation,incircle,exact_predicates,adaptive_precision_or_symbolic_perturbation)
 R6_CONSTRUCT = compute_cells_edges_vertices_and_adjacency
 R7_BOUNDARY = clip_or_restrict_unbounded_cells_if_required
 R8_DUAL = optionally_construct_or_validate_Delaunay_dual
 R9_COMPLEXITY = assess(input_size,dimension,output_size_and_algorithmic_cost)
 R10_VALIDATE = check_nearest_site_invariants_adjacency_bisectors_degeneracies_and_reproducibility
}

CONSTRAINTS {
 C1 = "Duplicate sites create undefined or redundant nearest-site ownership unless handled explicitly."
 C2 = "Cocircular sites can create higher-degree Voronoi vertices."
 C3 = "Floating-point incircle and orientation tests can corrupt adjacency near degeneracy."
 C4 = "Weighted Voronoi cells can be empty."
 C5 = "Unbounded cells require clipping when finite polygonal output is required."
 C6 = "Higher-dimensional Voronoi complexity can grow rapidly."
 C7 = "Non-Euclidean metrics change bisector shape and invalidate Euclidean assumptions."
 C8 = "Approximate construction can preserve coordinates while breaking combinatorial adjacency."
 C9 = "Fortune-style sweep implementations require careful event ordering and circle-event invalidation."
 C10 = "Randomised incremental algorithms require seed-aware reproducibility."
}

SEMANTIC_EQUIVALENCE {
 "VoronoiDiagram" <=> "VoronoiTessellation"
 "VoronoiDiagram" <=> "DirichletTessellation"
 "ThiessenPolygon" <=> "PlanarVoronoiCellInGeospatialContext"
 "PowerDiagram" <=> "LaguerreDiagram"
 "CentroidalVoronoiTessellation" <=> "CVT"
 "FortuneAlgorithm" <=> "FortuneSweep"
}

VALIDATION {
 V1 = "Dimension and site representation are explicit."
 V2 = "Distance metric and weighting are documented."
 V3 = "Duplicate-site policy is documented."
 V4 = "Degeneracy handling is explicit."
 V5 = "Precision and predicate model is documented."
 V6 = "Each cell satisfies nearest-site ownership under the declared metric."
 V7 = "Cell adjacency and shared boundaries are consistent."
 V8 = "Voronoi-Delaunay duality is checked where applicable."
 V9 = "Bounded-domain clipping is documented where used."
 V10 = "Results are reproducible under documented arithmetic, ordering and random-seed settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 VORONOI_DEFINITION = 0.99
 CELL_REASONING = 0.99
 DELAUNAY_DUALITY_REASONING = 0.99
 FORTUNE_ALGORITHM_REASONING = 0.98
 WEIGHTED_VORONOI_REASONING = 0.98
 HIGHER_DIMENSIONAL_REASONING = 0.97
 ROBUSTNESS_REASONING = 0.99
 POLICY = "Reduce confidence when metric, weighting, duplicate-site policy, degeneracy handling, precision model or bounding domain are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,OntologyGrounding,VoronoiReasoning,
  VoronoiCellReasoning,BisectorReasoning,
  DelaunayDualityReasoning,FortuneAlgorithmReasoning,
  WeightedVoronoiReasoning,PowerDiagramReasoning,
  OrderKVoronoiReasoning,CentroidalVoronoiReasoning,
  LloydAlgorithmReasoning,NearestNeighbourReasoning,
  FacilityLocationReasoning,MeshGenerationReasoning,
  RobustPredicateReasoning,DegeneracyReasoning,
  ComplexityReasoning,VerificationReasoning,
  KnowledgeGraphConstruction,RetrievalAugmentation,RecursiveInference
 ]
 NORMALISE {
  "Voronoi diagram" -> VoronoiDiagram
  "Voronoi tessellation" -> VoronoiDiagram
  "Dirichlet tessellation" -> VoronoiDiagram
  "Thiessen polygon" -> VoronoiCell
  "power diagram" -> PowerDiagram
  "Laguerre diagram" -> PowerDiagram
  "CVT" -> CentroidalVoronoiTessellation
 }
}

EXECUTION_RULES {
 E1 = "If space is partitioned by nearest-site ownership, activate VoronoiDiagramOntology2."
 E2 = "Define dimension, site representation, metric and weighting before construction."
 E3 = "Handle duplicate and degenerate sites explicitly."
 E4 = "For planar ordinary Euclidean diagrams, choose Fortune, Delaunay-dual, incremental or divide-and-conquer construction."
 E5 = "Use exact or adaptive orientation and incircle predicates near degeneracy."
 E6 = "Clip unbounded cells when a finite domain representation is required."
 E7 = "For weighted problems, distinguish additive, multiplicative and power-distance semantics."
 E8 = "Validate Voronoi-Delaunay duality where applicable."
 E9 = "Verify nearest-site ownership, adjacency, degeneracies and reproducibility."
}

RECURSION {
 ENTRY = VoronoiDiagram
 EXPAND(VoronoiDiagram) -> [
  VoronoiTessellation,VoronoiPartition,Site,Generator,SeedPoint,
  VoronoiCell,VoronoiRegion,VoronoiEdge,VoronoiVertex,
  VoronoiFace,VoronoiFacet,Bisector,PerpendicularBisector,
  EquidistanceLocus,NearestSite,NearestNeighbour,
  NearestSitePartition,EuclideanDistance,MetricDistance,
  WeightedVoronoiDiagram,AdditivelyWeightedVoronoi,
  MultiplicativelyWeightedVoronoi,PowerDiagram,LaguerreDiagram,
  ApolloniusDiagram,AnisotropicVoronoi,GeodesicVoronoi,
  RestrictedVoronoiDiagram,ClippedVoronoiDiagram,
  BoundedVoronoiCell,UnboundedVoronoiCell,
  OrderKVoronoiDiagram,FarthestPointVoronoiDiagram,
  DelaunayTriangulation,DelaunayEdge,DelaunayTriangle,
  DelaunayDuality,EmptyCircumcircleProperty,
  Circumcenter,Circumcircle,Circumsphere,
  GeneralPosition,Degeneracy,Cocircularity,DuplicateSite,
  FortuneAlgorithm,FortuneSweep,BeachLine,ParabolicArc,
  SiteEvent,CircleEvent,EventQueue,IncrementalVoronoi,
  RandomisedIncrementalVoronoi,DivideAndConquerVoronoi,
  HalfPlaneIntersection,VoronoiFromDelaunay,
  HigherDimensionalVoronoi,VoronoiPolytope,
  CentroidalVoronoiTessellation,CVT,LloydAlgorithm,
  DirichletTessellation,ThiessenPolygon,
  NearestNeighbourSearch,PointLocation,FacilityLocation,
  CoverageProblem,Quantisation,VectorQuantisation,
  MeshGeneration,NaturalNeighbourInterpolation,
  ComputationalComplexity,ExactPredicate,
  OrientationPredicate,IncirclePredicate,AdaptivePrecision,
  FloatingPointFilter,SymbolicPerturbation,NumericalRobustness,
  DynamicVoronoi,KineticVoronoi,ParallelVoronoi,
  Verification,Benchmarking,ReferenceResult,Reproducibility
 ]
 EXPAND(VoronoiFamilies) -> [
  OrdinaryEuclideanVoronoi,
  WeightedAndPowerVoronoi,
  HigherOrderVoronoi,
  FarthestPointVoronoi,
  RestrictedAndClippedVoronoi,
  CentroidalVoronoi,
  HigherDimensionalVoronoi,
  DynamicAndParallelVoronoi
 ]
 STOP_CONDITION = "Stop when sites, metric, weighting, cells, adjacency, construction method, robustness, duality, complexity and validation are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Geometry Ontology 2"
 RELATED_ONTOLOGIES = [
  "Computational Geometry Ontology 2",
  "Computational Geometry",
  "Convex Hull Ontology 2",
  "Delaunay Triangulation Ontology",
  "Nearest Neighbour Ontology",
  "Coordinate Geometry Ontologies",
  "Optimisation Computation",
  "Numerical Stability Ontology 2",
  "Floating Point Arithmetic Ontology",
  "Discrete Mathematics Ontologies",
  "Computational Topology Ontologies"
 ]
 ROUTE_RULES = [
  "Voronoi Diagram -> Computational Geometry Ontology 2 for parent semantics",
  "Voronoi Diagram -> Convex Hull for convex-cell and duality relationships",
  "Voronoi Diagram -> Delaunay Triangulation for geometric dual structure",
  "Voronoi Diagram -> Nearest Neighbour for nearest-site query semantics",
  "Voronoi Diagram -> Coordinate Geometry for metric and bisector representations",
  "Voronoi Diagram -> Optimisation Computation for facility-location and quantisation relationships",
  "Voronoi Diagram -> Numerical Stability for robust predicates",
  "Voronoi Diagram -> Floating Point Arithmetic for precision-sensitive event and incircle tests",
  "Voronoi Diagram -> Discrete Mathematics for cell-adjacency combinatorics",
  "Voronoi Diagram -> Computational Topology for complex and adjacency structure"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible Voronoi variants, construction algorithms or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve site-versus-cell distinction.",
  "Preserve metric-versus-weighting distinction.",
  "Preserve Voronoi-versus-Delaunay distinction.",
  "Preserve bounded-versus-unbounded cell distinction.",
  "Preserve ordinary-versus-weighted Voronoi distinction.",
  "Preserve geometric-coordinate-versus-combinatorial-adjacency distinction.",
  "Preserve exact-versus-approximate construction distinction.",
  "Preserve machine-readable Voronoi semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "A Voronoi diagram partitions space into regions whose points are nearest to corresponding generating sites."
 CELL_SUMMARY = "Each Voronoi cell consists of points no farther from its site than from competing sites."
 DUALITY_SUMMARY = "Voronoi adjacency is dual to Delaunay connectivity under standard assumptions."
 ALGORITHM_SUMMARY = "Planar diagrams can be constructed by Fortune's sweep, incremental, divide-and-conquer or Delaunay-dual methods."
 WEIGHTED_SUMMARY = "Weighted Voronoi variants modify the effective distance rule and can change cell geometry or produce empty cells."
 CENTROIDAL_SUMMARY = "Centroidal Voronoi tessellations place generators at cell centroids and can be approximated by Lloyd iteration."
 VALIDATION_SUMMARY = "Voronoi results should be checked for nearest-site ownership, boundary equidistance, adjacency, Delaunay duality, degeneracy handling and reproducibility."
}

FLOW {
 INPUT
 -> detect_Voronoi_context
 -> identify_dimension_sites_metric_weighting_bounding_domain_degeneracy_risk_and_output_requirements
 -> preprocess_duplicate_sites_and_define_distance_conventions
 -> classify_ordinary_weighted_power_order_k_farthest_restricted_geodesic_or_centroidal_variant
 -> select_Fortune_incremental_divide_and_conquer_Delaunay_dual_or_higher_dimensional_algorithm
 -> configure_exact_adaptive_filtered_or_symbolic_predicate_robustness
 -> construct_Voronoi_cells_edges_vertices_and_adjacency
 -> clip_or_restrict_unbounded_cells_if_required
 -> optionally_construct_or_validate_Delaunay_dual
 -> assess_input_dimension_output_and_algorithmic_complexity
 -> verify_nearest_site_ownership_bisectors_adjacency_degeneracies_and_reproducibility
 -> route_to_related_computational_geometry_convex_hull_Delaunay_nearest_neighbour_coordinate_geometry_optimisation_stability_floating_point_discrete_mathematics_and_topology_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Voronoi Diagram Ontology 2 defines nearest-site partitions of geometric space. It supports Voronoi cells, edges, vertices and bisectors, ordinary Euclidean diagrams, L1 and L-infinity variants, additive and multiplicative weighting, power and Laguerre diagrams, Apollonius, geodesic, restricted and clipped Voronoi structures, order-k and farthest-point diagrams, Delaunay duality, circumcentres and empty-circle relationships, Fortune's sweep, incremental and divide-and-conquer construction, centroidal Voronoi tessellations and Lloyd relaxation, nearest-neighbour search, facility-location and quantisation relationships, natural-neighbour interpolation, exact predicates, degeneracy handling, higher-dimensional, dynamic and parallel variants, verification, benchmarking and reproducibility."
}

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

}

END_FLOW