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.

12 questions
Filter by
Sorted by
Tagged with
71 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
155 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
278 views

• 216
130 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:...
143 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 ...
• 577
887 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
215 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
19k 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