Introduction

Looking for pseudo-code for Fortune's algorithm can be an essential step in understanding the underlying mechanics of constructing Voronoi diagrams efficiently. Fortune's algorithm is a classic computational geometry algorithm optimized for building Voronoi diagrams in $O(n \log n)$ time, where $n$ is the number of input points. This article provides a detailed exploration of the mechanics of Fortune's algorithm with a focus on pseudo-code and associated explanations for each step.

Fortune's Algorithm: Overview

Fortune's algorithm utilizes a sweep line approach, sweeping a line through the plane and constructing the Voronoi diagram incrementally. The key components include:

• The Sweep Line: A horizontal line that moves from top to bottom.
• The Beach Line: A dynamic parabola arrangement that is the intersection of the sweep line with growing paraboloids centered at each site.
• Event Points: Two kinds of events are processed:
  • Site Events: Add a new arc to the beach line.
  • Circle Events: Remove arcs from the beach line, creating Voronoi vertices.

Technical Explanation

Key Structures

1. Event Queue: A priority queue sorted by the y-coordinate of events. Site events have higher priority if two events share the same y-coordinate.
2. Beach Line Status: A balanced tree structure such as a Red-Black tree to maintain the sequence of arcs on the beach line.
3. Voronoi Diagram: Dynamically updated as events are processed.

Algorithm Steps

1. Initialize the Event Queue with all site events.
2. Process Events until the event queue is empty:
   • Site Event:
     • Determine where the new arc will appear on the beach line.
     • Update the beach line and handle intersections.
     • Insert potential circle events into the event queue.
   • Circle Event:
     • Remove the disappearing arc from the beach line and update the Voronoi diagram with a vertex.
     • Remove outdated circle events from the queue.
3. Complete the Voronoi Diagram by connecting unbounded edges with the convex hull of the original points.

Pseudo-code

Here's the core pseudo-code that defines Fortune's algorithm: