# Questions tagged [voronoi-diagram]

Use for questions related to Voronoi diagram, such as computing its edges.

43 questions
0answers
16 views

### How can I find the biggest value of an array without processing all of it?

I am trying to find the "good" value of an array while trying to process as little of it as possible for performance reasons. I am trying to implement a voronoi with a fortune line and am trying to ...
1answer
28 views

### How can I find the right parabola that intersects on a new site event for the fortune line algorithm?

I am trying to implement my own voronoï in Unity3d ( in C# ) as I am not satisfied with the existing libs that I found ( they always tend to miss a piece of information on the output and / or tend to ...
1answer
61 views

### Upper-bound on the number of edges in the farthest-point voronoi diagram

I'm trying to prove that the number of edges in the farthest-point voronoi diagram of $n$ points is upper-bounded by $2n-3$ (as claimed by Computational Geometry: Algorithms and Applications). I could ...
1answer
32 views

### Partitions of a sphere into only 6 sided regions

Starting from some distribution of n points on a sphere (where n>3), if we take the Voronoi diagram on the sphere of those points, the resulting regions could have various numbers of sides. If we ...
1answer
20 views

### Voronoi Diagram point set input

Is it possible to make a Voronoi diagram out of a non-simple convex hull set of points or a non-simple polygon? I have a set of points that make up a convex hull, but within the set of points, there ...
1answer
25 views

### Why does a voronoi vertex have to be incident to at least three voronoi regions?

I am self-learning about Voronoi diagrams and in the book I am reading about, to prove Theorem 4.6, it assumes that the Voronoi vertex $v$ must be incidient to at least three Voronoi regions. That ...
1answer
48 views

### What is the average number of sides of a cell of a Voronoi pattern on a flat torus?

Consider a random voronoi pattern with a uniform distribution on a large flat torus. What are the average number of sides of a cell. My guess is 6. What about 3D or 4D? My guess for 4D would be 24. ...
0answers
54 views

### Find vertices of a Voronoi diagram of convex polygons

From a set of polygons guaranteed to be : Convex Full (no holes) Non-intersecting (polygons may share edges/points, but not penetrate each other) How do I find the vertices of the Voronoi diagram ...
0answers
48 views

2answers
68 views

2answers
149 views

### Delaunay triangulation: Finding all triangles with empty circumcircle

I have a set of points and I want to find all possible triangles which have empty circumcircle. I want to use Delaunay Triangulation. I have read some papers on the subject but I am not sure whether ...