{
  "id": "enwiki-001320640602",
  "slug": "fortune-s-algorithm",
  "title": "Fortune's algorithm",
  "qid": "",
  "lead": "Fortune's algorithm is a sweep line algorithm for generating a Voronoi diagram from a set of points in a plane using O(n log n) time and O(n) space. It was originally published by Steven Fortune in 1986 in his paper \"A sweepline algorithm for Voronoi diagrams.\"",
  "body": "Fortune's algorithm is a sweep line algorithm for generating a Voronoi diagram from a set of points in a plane using O(n&nbsp;log&nbsp;n) time and O(n) space. It was originally published by Steven Fortune in 1986 in his paper \"A sweepline algorithm for Voronoi diagrams.\" ===Pseudocode=== Pseudocode description of the algorithm. let \\scriptstyle *(z) be the transformation \\scriptstyle *(z)=(z_x,z_y+d(z)) , where \\scriptstyle d(z) is the Euclidean distance between and the nearest site let be the \"beach line\" let \\scriptstyle R_p be the region covered by site . let \\scriptstyle C_{pq} be the boundary ray between sites and . let \\scriptstyle S be a set of sites on which this algorithm is to be applied. let \\scriptstyle p_1,p_2,...,p_m be the sites extracted from with minimal -coordinate, ordered by -coordinate let DeleteMin( ) be the act of removing the lowest and leftmost site of (sort by y unless they're identical, in which case sort by x) let be the Voronoi map of which is to be constructed by this algorithm Q \\gets {p_1,p_2,\\dots,p_m,S} create initial vertical boundary rays \\scriptstyle C_{p_1,p_2}^0,C_{p_2,p_3}^0,\\dots,C_{p_{m-1},p_m}^0 T \\gets *(R_{p_1}),C_{p_1,p_2}^0,*(R_{p_2}),C_{p_2,p_3}^0,\\dots,*(R_{p_{m-1}}),C_{p_{m-1},p_m}^0,*(R_{p_m}) while not IsEmpty( ) do ← DeleteMin( ) case of is a site in \\scriptstyle *(V) : find the occurrence of a region \\scriptstyle *(R_q) in containing , bracketed by \\scriptstyle C_{rq} on the left and \\scriptstyle C_{qs} on the right create new boundary rays \\scriptstyle C_{pq}^- and \\scriptstyle C_{pq}^+ with bases replace \\scriptstyle *(R_q) with \\scriptstyle *(R_q),C_{pq}^-,*(R_p),C_{pq}^+,*(R_q) in delete from any intersection between \\scriptstyle C_{rq} and \\scriptstyle C_{qs} insert into any intersection between \\scriptstyle C_{rq} and \\scriptstyle C_{pq}^- insert into any intersection between \\scriptstyle C_{pq}^+ and \\scriptstyle C_{qs} is a Voronoi vertex in \\scriptstyle *(V) : let be the intersection of \\scriptstyle C_{qr} on the left and \\scriptstyle C_{rs} on the right let \\scriptstyle C_{uq} be the left neighbor of \\scriptstyle C_{qr} and let \\scriptstyle C_{sv} be the right neighbor of \\scriptstyle C_{rs} in if \\scriptstyle q_y = s_y , create a new boundary ray \\scriptstyle C_{qs}^0 else if is right of the higher of and , create \\scriptstyle C_{qs}^+ else create \\scriptstyle C_{qs}^- endif replace \\scriptstyle C_{qr},*(R_r),C_{rs} with newly created \\scriptstyle C_{qs} in delete from any intersection between \\scriptstyle C_{uq} and \\scriptstyle C_{qr} delete from any intersection between \\scriptstyle C_{rs} and \\scriptstyle C_{sv} insert into any intersection between \\scriptstyle C_{uq} and \\scriptstyle C_{qs} insert into any intersection between \\scriptstyle C_{qs} and \\scriptstyle C_{sv} record as the summit of \\scriptstyle C_{qr} and \\scriptstyle C_{rs} and the base of \\scriptstyle C_{qs} output the boundary segments \\scriptstyle C_{qr} and \\scriptstyle C_{rs} endcase endwhile output the remaining boundary rays in ==Weighted sites and disks== ==References== ==External links== Steven Fortune's C implementation Fortune's Voronoi algorithm implemented in C++ Fortune's algorithm implemented in JavaScript archived on GitHub as of August 2015 Fortune's Algorithm Visualization as of 2025 access is blocked",
  "categories": [
    "20477111",
    "23302980",
    "23603337",
    "26220375",
    "7692542"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1320640602",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1762382500.0,
  "claims": [
    {
      "id": 30532344,
      "subject_qid": "",
      "subject_slug": "fortune-s-algorithm",
      "predicate": "publication date",
      "object_text": "1986",
      "object_num": 19860000.0,
      "object_unit": null,
      "polarity": 1,
      "qualifier": "",
      "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1320640602",
      "source_name": "Wikipedia",
      "source_tier": 3,
      "retrieved_at": 1792493566.772927,
      "confidence": 0.95,
      "article_slug": "fortune-s-algorithm",
      "span_start": 18,
      "span_end": 67
    }
  ],
  "contradictions": [],
  "confidence": 0.95,
  "csl": {
    "id": "enwiki-001320640602",
    "type": "webpage",
    "title": "Fortune's algorithm",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/fortune-s-algorithm",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001320640602",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1320640602",
    "note": "Immutable snapshot enwiki-001320640602"
  }
}