---
title: Fortune's algorithm
slug: fortune-s-algorithm
qid: 
snapshot: enwiki-001320640602
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1320640602
tags: [20477111, 23302980, 23603337, 26220375, 7692542]
---

# Fortune's algorithm

> [!note] Provenance
> Snapshot `enwiki-001320640602` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1320640602> · Licensed CC BY-SA 4.0

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."

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
