Questions tagged [voronoi-diagrams]
For a given finite point set S, a voronoi diagram is a tessellation of a euclidean space. In the 2D case, it consists of conforming convex polygons surrounding each point such that for given a point p in S, any point in the enclosing polygon is closer to p than any other point in S.
13 questions
0
votes
1
answer
68
views
Computing a power diagram
I want to compute the power diagram of a set of points. When the d-spheres overlap, the solution seems straightforward. You construct the d-1 sphere made up by their intersection and then pass a plane ...
- 379
0
votes
0
answers
226
views
Producing Voronoi diagram in three dimensional
A Voronoi diagram is a kind of tesselation that divided the medium into polygons in 2D and polyhedrons in 3D.
Although there are many algorithms to construct a Voronoi diagram, some of them are faster ...
- 11
1
vote
0
answers
277
views
Fortune algorithm for voronoi diagram
Although there are many algorithms to construct Voronoi diagram, some of them are faster than others. Based on my knowledge Fortune algorithm is fastest for construct Voronoi diagram either in two ...
- 11
7
votes
0
answers
302
views
Finding points inside cells of power (generalized Voronoi) diagram
Suppose we have a set of points $p_1,\ldots,p_n\in\mathbb R^d$ as well as a set of weights $w_1,\ldots,w_n\in\mathbb R$. Recall that the power cell associated to the pair $(p_k,w_k)$ is given by:
$$\...
- 1,433
0
votes
0
answers
279
views
Can I use matplotlib to plot the surface of a 3D body?
If Matplotlib could volume render, I would not ask this question. But it can't. Can I however instead use Matplotlib to plot the surface of a 3D body? I.e. is there a way to (i) triangulate the ...
- 11
5
votes
1
answer
1k
views
How can one prove the duality of Voronoi and Delaunay?
Hoping I'm not misunderstanding the concept here, but it is my understanding that Voronoi Diagrams and Delaunay Tesselations are 'dual' to one another, owing to the fact that each' solution makes ...
- 151
0
votes
1
answer
357
views
Elliptic PDE finite volume method with Dirichlet boundary condition
I want to discretize the following equation using a Finite Volume Method
$$\nabla \cdot (a(x)\nabla u)=f(x)\\x\in \Omega \subset \mathbb{R}^2
\\u_{|\partial\Omega}=g$$
I'm using Voronoi cells here: ...
- 226
4
votes
0
answers
194
views
Fast Algorithms for the Simplicial Decomposition of a Convex Polytope in N-Dimensions
I'm in the process of constructing an algorithm which computes the Voronoi diagram of a set of points, but I now need a method to decompose each Voronoi cell into simplices. The information we have is:...
- 41
0
votes
3
answers
167
views
Polynomial reconstruction on unstructured grids
For a 1D grid I can calculate a Lagrange polynomial through an arbitrary set of points for the reconstruction of a polynomial function.
In 2D I have an unstructured grid and want to interpolate the ...
- 617
8
votes
5
answers
1k
views
Computing the Voronoi diagram of a region inside a box
I am facing a problem as follows: I have a box full of points with a certain unknown distribution and I would like to calculate its Voronoï Diagram. The problem is that the number of points is so huge ...
- 183
5
votes
2
answers
238
views
Restrict Voronoï diagram to a polygon
I managed to build the Voronoï diagram of n points using Fortune's algorithm.
This gives me a set of half-edges, some of which being infinite (no starting point and/or no end point).
I'd like to ...
- 151
29
votes
5
answers
21k
views
Fastest Delaunay triangulation libraries for sets of 3D points
Which is the fastest library for performing delaunay triangulation of sets with millions if 3D points? Are there also GPU versions available? From the other side, having the voronoi tessellation of ...
- 711
10
votes
5
answers
7k
views
How are the Voronoi Tesselation and Delaunay triangulation problems duals of each other?
I have always been told that the Voronoi diagram is the dual of the Delaunay triangulation problem. In what sense can they be duals of each other? I thought that dual problems (i.e. in linear ...
- 12.2k