Voronoi Diagram Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the mathematical ontology of Voronoi diagrams within the Kireth Research Semantic Library. A Voronoi diagram partitions a metric space into regions associated with sites, where each region consists of points at least as close to its generating site as to any other. In computational geometry, Voronoi diagrams provide a fundamental structure for proximity, nearest-neighbour reasoning, spatial subdivision, Delaunay duality, medial-axis relations, facility location, interpolation, meshing and geometric optimisation. This ontology supports planar and higher-dimensional Voronoi diagrams, cells, edges, vertices, bisectors, nearest sites, degeneracies, weighted variants, construction algorithms and relationships with Delaunay triangulations and spatial search.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = VoronoiDiagram
 SYMBOLIC_FORMS = [
  "Vor(S)",
  "V(S)",
  "Vor(p_i)={x:d(x,p_i)<=d(x,p_j) for all j}"
 ]
 ENTITY_CLASS = ProximitySubdivision
 PRIMARY_CONTEXT = ComputationalGeometry
 DEFINITION = "A Voronoi diagram is a partition of a metric space into cells determined by nearest-site ownership."
 SEMANTIC_ROLE = "Provides the canonical nearest-neighbour subdivision framework for proximity, spatial partitioning, Delaunay duality, point location, facility placement and geometric optimisation."
}

SCOPE {
 INCLUDE = [
  VoronoiDiagram,
  Site,
  VoronoiCell,
  VoronoiEdge,
  VoronoiVertex,
  Bisector,
  NearestSite,
  NearestNeighbour,
  PlanarVoronoiDiagram,
  HigherDimensionalVoronoiDiagram,
  EuclideanVoronoiDiagram,
  WeightedVoronoiDiagram,
  AdditivelyWeightedVoronoiDiagram,
  MultiplicativelyWeightedVoronoiDiagram,
  PowerDiagram,
  FarthestPointVoronoiDiagram,
  VoronoiNeighbour,
  DelaunayTriangulation,
  Circumcircle,
  EmptyCircleProperty,
  PointLocation,
  IncrementalConstruction,
  DivideAndConquer,
  FortuneAlgorithm,
  Degeneracy,
  CocircularSites,
  CoincidentSites
 ]

 EXCLUDE_AS_PRIMARY = [
  ArbitrarySpatialPartitionWithoutNearestSiteRule,
  DirichletDomainWithoutGeometricContext,
  GeneralClusteringUnlessNearestSitePartitionIsCentral,
  DelaunayTriangulationExceptAsDualStructure
 ]

 DISAMBIGUATION_RULE =
  "When space is partitioned according to which site is nearest under a specified metric, interpret the structure as a Voronoi diagram."
}

CORE_CONCEPTS {

 VoronoiDiagram {
  definition = "The collection of Voronoi cells induced by a set of sites under a metric."
 }

 Site {
  definition = "A generating point or object whose nearest-region ownership defines a Voronoi cell."
 }

 VoronoiCell {
  definition = "The set of points at least as close to one site as to every other site."
 }

 VoronoiEdge {
  definition = "A boundary locus where two sites are equally nearest under generic planar conditions."
 }

 VoronoiVertex {
  definition = "A point equidistant from three or more sites under planar Euclidean conditions."
 }

 Bisector {
  definition = "The locus of points equidistant from two sites."
 }

 NearestSite {
  definition = "A site minimising the distance from a query point."
 }

 DelaunayTriangulation {
  definition = "The geometric dual of the Voronoi diagram under compatible Euclidean assumptions."
 }

 PowerDiagram {
  definition = "A weighted Voronoi variant based on power distance."
 }

 FarthestPointVoronoiDiagram {
  definition = "A subdivision according to farthest-site ownership rather than nearest-site ownership."
 }
}

RELATIONS {
 VoronoiDiagram --is_subdivision_of--> MetricSpace
 VoronoiDiagram --is_generated_by--> SiteSet
 VoronoiCell --is_associated_with--> Site
 VoronoiEdge --separates--> VoronoiCells
 VoronoiVertex --is_incident_to--> VoronoiEdges
 VoronoiEdge --lies_on--> Bisector
 VoronoiCell --contains--> PointsNearestToSite
 VoronoiDiagram --supports--> NearestNeighbour
 VoronoiDiagram --supports--> PointLocation
 VoronoiDiagram --is_dual_to--> DelaunayTriangulation
 VoronoiVertex --corresponds_to--> DelaunayFace
 VoronoiEdge --corresponds_to--> DelaunayEdge
 VoronoiNeighbour --corresponds_to--> DelaunayAdjacentSite
 CocircularSites --cause--> VoronoiDegeneracy
}

OPERATORS {
 VORONOI_CELL(p_i,S,d) :=
  {x : d(x,p_i)<=d(x,p_j) for all p_j in S}

 VORONOI_DIAGRAM(S,d) :=
  union_of_cells VORONOI_CELL(p_i,S,d)

 NEAREST_SITE(x,S,d) :=
  argmin_{p in S} d(x,p)

 BISECTOR(p_i,p_j,d) :=
  {x : d(x,p_i)=d(x,p_j)}

 ARE_VORONOI_NEIGHBOURS(p_i,p_j) :=
  closures_of_cells_share_boundary_of_positive_dimension

 VORONOI_VERTEX(S_subset) :=
  point_equidistant_from_sites_in_S_subset
  AND locally_no_closer_other_site

 DUAL_DELAUNAY_EDGE(p_i,p_j) :=
  edge(p_i,p_j)
  WHEN VoronoiCells(p_i,p_j) share_edge

 POWER_DISTANCE(x,p,w) :=
  ||x-p||^2-w

 POWER_CELL(p_i,w_i,S) :=
  {x : power_distance(x,p_i,w_i)<=power_distance(x,p_j,w_j) for_all_j}

 POINT_LOCATION(x,Vor) :=
  cell_edge_vertex_or_outside_classification
}

DEFINITIONS {
 D1 = "Each Voronoi cell consists of points nearest to its generating site."
 D2 = "Voronoi cell boundaries arise from pairwise distance equality."
 D3 = "In generic planar Euclidean position, Voronoi vertices are equidistant from three sites."
 D4 = "Planar Voronoi edges are portions of perpendicular bisectors between sites."
 D5 = "The Delaunay triangulation is dual to the planar Voronoi diagram."
 D6 = "Cocircular site configurations produce non-simplicial Delaunay degeneracies and higher-degree Voronoi vertices."
 D7 = "Voronoi diagrams depend on the chosen metric."
 D8 = "Weighted Voronoi variants change the distance or ownership rule."
 D9 = "Voronoi cells may be bounded or unbounded."
 D10 = "Nearest-neighbour queries can be interpreted through Voronoi cell membership."
}

AXIOMS {
 A1_NEAREST_SITE:
  Every point in a Voronoi cell is no farther from its site than from any competing site

 A2_COVERAGE:
  Voronoi cells cover the ambient domain under the chosen site and metric model

 A3_BOUNDARY_EQUALITY:
  Shared cell boundaries consist of points with equal relevant distance to multiple sites

 A4_CELL_CONVEXITY_EUCLIDEAN_POINT_SITES:
  For unweighted point sites under Euclidean distance, Voronoi cells are convex

 A5_DUALITY:
  Under standard planar Euclidean assumptions, Voronoi adjacency corresponds to Delaunay edges

 A6_VERTEX_CIRCUMCENTER:
  A generic planar Voronoi vertex is the circumcenter of its corresponding Delaunay triangle

 A7_EMPTY_CIRCLE:
  The circumcircle corresponding to a Voronoi vertex contains no site in its interior under standard Delaunay conditions

 A8_METRIC_DEPENDENCE:
  Changing the metric can change bisectors, cells and diagram topology
}

REASONING {

 R1_CELL_MEMBERSHIP {
  INPUT = [query_point_x,site_set_S]
  COMPUTE = distances_to_sites
  IDENTIFY = minimum_distance_sites
  RETURN = containing_cell_or_boundary
 }

 R2_BISECTOR {
  INPUT = [site_p,site_q,metric_d]
  SOLVE = d(x,p)=d(x,q)
  RETURN = bisector_geometry
 }

 R3_PLANAR_CONSTRUCTION {
  INPUT = planar_sites
  IDENTIFY = degeneracies
  SELECT = Fortune_divide_and_conquer_incremental_or_Delaunay_dual_method
  COMPUTE = cells_edges_vertices
  VERIFY = nearest_site_conditions
  RETURN = VoronoiDiagram
 }

 R4_DELAUNAY_DUALITY {
  INPUT = VoronoiDiagram
  FOR each_adjacent_cell_pair
   CONNECT = generating_sites
  RETURN = Delaunay_structure
 }

 R5_VERTEX_REASONING {
  INPUT = candidate_point_v_and_sites
  TEST = equal_distance_to_incident_sites
  TEST = no_other_site_closer
  RETURN = VoronoiVertexOrNot
 }

 R6_NEAREST_NEIGHBOUR {
  INPUT = [query_point_x,VoronoiDiagram]
  LOCATE = containing_cell
  RETURN = generating_site_of_cell
 }

 R7_WEIGHTED_VORONOI {
  INPUT = sites_weights_and_weight_model
  DEFINE = weighted_distance_rule
  CONSTRUCT = weighted_cells
  RETURN = weighted_diagram
 }

 R8_POINT_LOCATION {
  INPUT = query_point_and_preprocessed_diagram
  SEARCH = spatial_index_or_planar_point_location_structure
  RETURN = cell_edge_or_vertex
 }

 R9_DEGENERACY {
  INPUT = site_set
  DETECT = duplicates_collinearity_cocircularity_or_metric_ties
  APPLY = declared_symbolic_perturbation_or_multi_incidence_policy
  RETURN = convention_consistent_diagram
 }
}

CONSTRAINTS {
 C1 = "Voronoi geometry depends on the chosen metric."
 C2 = "Coincident sites require explicit duplicate-site handling."
 C3 = "Cocircular sites can create Voronoi vertices incident to more than three cells."
 C4 = "Generic planar claims must not be applied silently to degenerate input."
 C5 = "Weighted Voronoi variants are not interchangeable."
 C6 = "Nearest-site ties place points on cell boundaries."
 C7 = "Unbounded cells are valid and often correspond to convex-hull sites."
 C8 = "Delaunay duality assumptions must match the Voronoi metric and weighting model."
 C9 = "Floating-point distance comparisons and incircle predicates may require robust arithmetic."
}

SEMANTIC_EQUIVALENCE {
 "VoronoiDiagram" <=> "NearestSiteSubdivision"
 "VoronoiCell" <=> "NearestSiteRegion"
 "VoronoiEdge" <=> "SharedNearestSiteBoundary"
 "VoronoiVertex" <=> "MultiSiteEquidistanceVertex"
 "DirichletTessellation" <=> "VoronoiDiagram" WHEN standard_point_site_context
 "ThiessenPolygonDiagram" <=> "VoronoiDiagram" WHEN planar_application_context
}

VALIDATION {
 V1 = "Every cell point satisfies nearest-site inequality."
 V2 = "Cell boundaries satisfy equal-distance conditions."
 V3 = "Cells cover the intended domain."
 V4 = "Generic planar vertices correspond to circumcentres."
 V5 = "Voronoi-Delaunay adjacency is consistent."
 V6 = "Weighted variants use the declared distance model."
 V7 = "Degeneracies follow declared policy."
 V8 = "Nearest-neighbour answer matches cell ownership."
 V9 = "Robust predicates maintain combinatorial consistency."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 VORONOI_DEFINITION = 0.99
 CELL_MEMBERSHIP_REASONING = 0.99
 PLANAR_CONSTRUCTION_REASONING = 0.99
 DUALITY_REASONING = 0.99
 VERTEX_REASONING = 0.99
 WEIGHTED_REASONING = 0.98
 DEGENERACY_REASONING = 0.99
 ROBUSTNESS_REASONING = 0.99

 POLICY =
  "Reduce confidence when metric, weighting model, site type, degeneracy policy, ambient dimension or numeric precision assumptions are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  VoronoiReasoning,
  ComputationalGeometryReasoning,
  NearestNeighbourReasoning,
  SpatialSubdivisionReasoning,
  BisectorReasoning,
  DelaunayDualityReasoning,
  PointLocationReasoning,
  WeightedVoronoiReasoning,
  FacilityLocationReasoning,
  RobustPredicateReasoning,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "Voronoi diagram" -> VoronoiDiagram
  "Voronoi tessellation" -> VoronoiDiagram
  "Dirichlet tessellation" -> VoronoiDiagram
  "Thiessen polygons" -> VoronoiDiagram
  "Voronoi cell" -> VoronoiCell
  "Voronoi edge" -> VoronoiEdge
  "Voronoi vertex" -> VoronoiVertex
  "nearest-site diagram" -> VoronoiDiagram
  "power diagram" -> PowerDiagram
 }

 INTERPRETATION_ORDER = [
  detect_Voronoi_context,
  identify site_set_dimension_metric_and_weight_model,
  identify cell_edge_vertex_nearest_neighbour_duality_or_construction goal,
  identify degeneracy_and_precision assumptions,
  apply nearest_site_bisector_or_dual reasoning,
  verify coverage_distance_duality_and_robustness constraints,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("Voronoi diagram")
  OR nearest_site_partition_context
  THEN activate(VoronoiDiagramOntology)

 E2:
  IF cell_membership_requested
  THEN compare query_distance_to_all_relevant_sites

 E3:
  IF nearest_neighbour_requested
  AND Voronoi_structure_available
  THEN locate query_point_in_diagram

 E4:
  IF planar_construction_requested
  THEN select Fortune_divide_and_conquer_incremental_or_Delaunay_dual pathway

 E5:
  IF Delaunay_dual_requested
  THEN connect sites whose Voronoi cells share appropriate boundary

 E6:
  IF weighted_context
  THEN identify additive_multiplicative_or_power distance model before construction

 E7:
  IF cocircular_or_tied_configuration
  THEN apply explicit degeneracy policy

 E8:
  IF numeric_predicates_near_degenerate
  THEN use robust_or_adaptive arithmetic
}

RECURSION {
 ENTRY = VoronoiDiagram

 EXPAND(VoronoiDiagram) -> [
  Site,
  VoronoiCell,
  VoronoiEdge,
  VoronoiVertex,
  Bisector,
  NearestSite,
  NearestNeighbour,
  PlanarVoronoiDiagram,
  HigherDimensionalVoronoiDiagram,
  WeightedVoronoiDiagram,
  PowerDiagram,
  FarthestPointVoronoiDiagram,
  DelaunayTriangulation,
  PointLocation,
  ConstructionAlgorithm,
  Degeneracy
 ]

 EXPAND(ConstructionAlgorithm) -> [
  FortuneAlgorithm,
  DivideAndConquer,
  IncrementalConstruction,
  DelaunayDualConstruction
 ]

 EXPAND(WeightedVoronoiDiagram) -> [
  AdditivelyWeightedVoronoiDiagram,
  MultiplicativelyWeightedVoronoiDiagram,
  PowerDiagram
 ]

 EXPAND(Degeneracy) -> [
  CoincidentSites,
  CocircularSites,
  DistanceTie,
  SymbolicPerturbation,
  MultiIncidenceVertex
 ]

 STOP_CONDITION =
  "Stop when the Voronoi diagram, cell ownership, adjacency, bisector, dual Delaunay relation, nearest-neighbour result, weighting model, construction or degeneracy treatment is sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Computational Geometry"

 IMMEDIATE_CONTEXTS = [
  "Computational Geometry Ontology",
  "Delaunay Triangulation Ontology",
  "Convex Hull Ontology",
  "Point Location Ontologies"
 ]

 RELATED_ONTOLOGIES = [
  "Computational Geometry",
  "Computational Geometry Ontology",
  "Delaunay Triangulation Ontology",
  "Convex Hull Ontology",
  "Coordinate Geometry Ontology",
  "Vector Geometry Ontology",
  "Metric Space Ontologies",
  "Nearest Neighbour Ontologies",
  "Spatial Data Structure Ontologies",
  "Optimisation Ontologies"
 ]

 ROUTE_RULES = [
  "Voronoi Diagram -> Computational Geometry Ontology for parent algorithmic semantics",
  "Voronoi Diagram -> Delaunay Triangulation for planar duality",
  "Voronoi Diagram -> Convex Hull for unbounded-cell and lifting relationships",
  "Voronoi Diagram -> Coordinate Geometry for bisector equations",
  "Voronoi Diagram -> Metric Space for nearest-site semantics",
  "Voronoi Diagram -> Spatial Data Structures for point-location and nearest-neighbour queries",
  "Voronoi Diagram -> Optimisation for facility-location and nearest-site objectives"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

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

 RULES = [
  "Preserve nearest-site partition semantics.",
  "Preserve explicit metric dependence.",
  "Preserve cell-boundary equidistance semantics.",
  "Preserve Delaunay duality only under compatible assumptions.",
  "Preserve weighted-variant distinction.",
  "Preserve degeneracy handling.",
  "Preserve unbounded-cell validity.",
  "Preserve machine-readable Voronoi semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "A Voronoi diagram partitions space into cells consisting of points nearest to individual generating sites."

 CELL_SUMMARY =
  "Vor(p_i)={x:d(x,p_i)<=d(x,p_j) for all j}."

 EDGE_SUMMARY =
  "A Voronoi edge is a locus where two sites are equally nearest under generic planar conditions."

 VERTEX_SUMMARY =
  "A generic planar Voronoi vertex is equidistant from three sites and corresponds to a Delaunay circumcentre."

 DUALITY_SUMMARY =
  "Two sites are Delaunay adjacent when their Voronoi cells share an edge under standard planar assumptions."

 NEAREST_NEIGHBOUR_SUMMARY =
  "The site owning the cell containing a query point is a nearest neighbour."

 WEIGHTED_SUMMARY =
  "Weighted Voronoi diagrams alter the distance or ownership rule and must retain their declared weighting model."

 ROBUSTNESS_SUMMARY =
  "Reliable construction requires explicit handling of duplicate, cocircular and numerically near-degenerate sites."
}

FLOW {
 INPUT
 -> detect_Voronoi_context
 -> identify sites_dimension_metric_weight_model_and_query_goal
 -> identify degeneracy_ties_and_numeric_precision assumptions
 -> choose cell_membership_bisector_construction_nearest_neighbour_or_Delaunay_duality pathway
 -> compute Voronoi_cells_edges_vertices_or_query result
 -> verify nearest_site_coverage_adjacency_duality_and_robustness constraints
 -> route to computational_geometry Delaunay convex_hull coordinate metric_space spatial_index_or_optimisation ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Voronoi Diagram Ontology defines nearest-site subdivisions of space and supports Voronoi cells, edges, vertices, bisectors, nearest-neighbour queries, weighted variants, point location, construction algorithms, degeneracy handling and the dual relationship with Delaunay triangulations."
}

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

}

END_FLOW