# What Type of Math is Used in Fortune's Algorithm?

• MHB
• RidiculousName
In summary, the conversation discusses Fortune's Algorithm, which is known as the fastest algorithm for generating a voronoi diagram. The speaker is interested in learning about procedural generation and asks about the required mathematical knowledge to understand the algorithm. They also mention a pseudocode version and suggest looking into the sweep line algorithm and computational geometry. Additionally, they suggest looking at a text on this topic and trying to come up with an algorithm from the gif on the algorithm's wiki page.
RidiculousName
I've heard that Fortune's Algorithm is the fastest algorithm yet found to generate a voronoi diagram. I am far from being able to understand it, but I got interested in it because I want to learn about procedural generation. My question is, what sort of mathematics would I have to be familiar with to understand it?

In case you are unfamiliar with it, there is a pseudocode version here.
I can't copy/paste it because it has unusual characters that don't seem to translate on this forum.

You could look into the sweep line algorithm first, and then go back to how the diagram is generated. This algorithms hail from the realm of "computational geometry". It might be useful to look at a text on this topic.

Another thing I would try to do is just try come up with an algorithm yourself from looking at the gif in the wiki page.

## 1. What is Fortune's Algorithm?

Fortune's Algorithm is a computational geometry algorithm used to construct Voronoi diagrams. These diagrams are a way to partition a given space into regions based on the proximity to a set of points.

## 2. What type of math is used in Fortune's Algorithm?

Fortune's Algorithm uses a variety of mathematical concepts, including plane sweep, binary search trees, and parabolas. It also involves a lot of basic geometry and trigonometry.

## 3. How does Fortune's Algorithm work?

Fortune's Algorithm works by sweeping a vertical line across the plane and keeping track of the closest site to each point on the line. This creates a series of parabolic arcs that intersect and form the edges of the Voronoi diagram.

## 4. What is the main application of Fortune's Algorithm?

The main application of Fortune's Algorithm is in computer graphics and computer aided design. It is used to create smooth and accurate boundaries between objects in digital images or models.

## 5. Are there any limitations to Fortune's Algorithm?

Fortune's Algorithm can only be used for two-dimensional spaces and is not applicable to higher dimensions. It also requires a significant amount of computational power and can be slow for large datasets.

Replies
5
Views
1K
Replies
1
Views
2K
Replies
6
Views
7K
Replies
6
Views
1K
Replies
3
Views
700
Replies
8
Views
2K
Replies
13
Views
2K
Replies
2
Views
2K
Replies
1
Views
1K
Replies
7
Views
2K