Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [voronoi-diagram]

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

0
votes
1answer
24 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 ...
4
votes
1answer
43 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. ...
0
votes
0answers
34 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 ...
0
votes
0answers
43 views

Delaunay triangulation in $\mathbb R^d$: Empty sphere property works for all $k$-faces?

This is (it seems to me) a well-known fact, but I am struggling to find a reference. Let $X=\{x_1,\dots, x_n\}\subset \mathbb R^d$ be a set of points. Then the following is true: Subset $F\subset ...
1
vote
0answers
26 views

Clarification on How to derive Voronoi diagram from Delaunay triangulation in linear time

Definitions: Assume that a set of points $P=\{p_1,\dots,p_n\}$ in $\mathbb R^d $ is given. For each $p_i \in P$, the Voronoi region of $p_i$ is defined as: $Vor(p_i)=\{p\in\mathbb R^d:\forall p_j\in ...
5
votes
2answers
63 views

Given the Voronoi diagram of some points on a line, determine the points

Definition: Assume that a set of points $P=\{p_1,\dots,p_n\}$ on a line is given. The Voronoi diagram of $P$ is a set of points $V(P)=\{x_1,\dots,x_{n-1}\}$ such that $x_i$ is the midpoint of $p_i p_{...
11
votes
1answer
183 views

Voronoi cell volume inside the ball

I have the following problem: Let us denote a ball with center $C$ and radius $R$ in $\mathbb{R}^d$ as $B(C, R)$. Given a unit ball $B(0, 1)$ and vector $u$ has a uniform distribution inside the ...
1
vote
2answers
56 views

Circle given 2 points and tangent in Fortune's Voronoi Algorithm

Bisector approximation Hello I am trying to understand and implement an adaption of Fortune's algorithm for Voronoi Diagrams regarding its extension to handling lines, but I am stuck on the ...
4
votes
1answer
59 views

Is every planar graph a possible dual graph of a voronoi diagram? [closed]

My question is: Given a planar graph defined by its adjacency matrix. Can I always find a set of points, so that the dual graph of the voronoi diagram of that set of points is the same as the planar ...
0
votes
0answers
58 views

Perimeter of the intersection of Voronoi cell and Circle

Suppose there are some Poisson Voronoi cells generated by a homogeneous Poisson Point Process with density $\lambda$ and Voronoi partitioning. For an arbitrary cell region, consider a circle with ...
0
votes
0answers
12 views

How to compute the Centoid Voronio Diagram (VVD) edge lines equations in standard form

I'm currently writing a multiple swarm control algorithm for which I need to compute the Voronoi cells. To do this, I need to calculate the line equations for the Voronoi cell edges. I know that the ...
1
vote
0answers
14 views

Are all graphs induces on Voronoi of ALL metrics are planar?

Graph induced by Voronoi on Euclidean distance is planar (Delaunay triangulation). Is it true for other distance metrics : L_p where $1\leq p \leq \inf$? It seems to be true by definition of Voronoi, ...
1
vote
0answers
143 views

Properties of Voronoi on Manhattan distance

There are bunch of information on properties of Voronoi on Euclidean distance, but I cannot find any properties on Voronoi for Manhattan distance. For example in Euclidean Voronoi on average every ...
0
votes
0answers
126 views

Why brute-force Voronoi diagram computation takes $O(n^3)$

Professor told us that brute-force construction of Voronoi diagram takes $O(n^3)$. I do not understand why not $O(n^2)$. For any given point we need to find a bisector with every other point in a set. ...
0
votes
1answer
264 views

How can I merge 2 Delaunay triangulations / Voronoï diagrams?

I am building a Voronoï diagram using both Delaunay triangulation and a divide and conquer paradigm but how can I merge multiple diagrams efficiently ? As shown in this picture, I can make Voronoï ...
1
vote
1answer
63 views

Voronoi tessellation with known cell areas and unknown seeds

I would like to create a Voronoi tessellation inside a square of known dimensions. I know that I can plot a set of known seeds that will result in a set of cells with discrete areas; however, is it ...
1
vote
1answer
274 views

Given a Voronoi diagram created in $\mathcal{O}(n)$, is it possible to find the closest pair of points in $\mathcal{O}(n)$?

So given a set of points n there is a Voronoi-diagram given which was created in $\mathcal{O}(n)$. Now is it possible to find the closest pair of points of this set in $\mathcal{O}(n)$? I know that ...
1
vote
2answers
267 views

In Fortune's algorithm, how can I determine the arc of the beach line that intersects a given vertical line?

I'm trying to implement Fortune's algorithm to construct a Voronoi diagram. I'm having trouble finding the parabola right above a seed point. How can I know which parabola will a vertical line (from ...
0
votes
2answers
450 views

$\{0, 1\}^n$ notation

Can anybody explain me what it means the following: $\mathtt{for} \quad \mathbf{p} \quad \mathtt{in} \quad \{\{0, 1\}^k \setminus \mathbf{0}\} \quad \mathtt{do}$ See here https://cseweb.ucsd.edu/~...
5
votes
1answer
155 views

Scale dependence of Voronoi path length

Consider a square of fixed size in Euclidean space. Assume the square has been decomposed into Voronoi blocks of a certain average area. Now assume you can only move along the edges of the Voronoi ...
3
votes
2answers
239 views

Split a cell in voronoi diagram

My work involves using voronoi diagrams, and my next task is to split a cell inside this diagram in half(aprox.) More accurately: I have a set of (x,y) points, I am using a library which takes care ...
0
votes
0answers
135 views

Discretization of Continuous State Space Markov Chain

I am investigating a model, in which we are considering a discrete time gaussian random walk $(\Phi_k)_{k\geq{1}}$, which has state space $V\subset{\mathbb{R}^d}$. I have formed a tessellation of the ...
1
vote
0answers
123 views

Is there a proof of the Green-Sibson algorithm?

I was introduced to Voronoi Diagram and espacially the Green-Sibson algorithm (Here). I couldn't find their paper so I'm looking for a proof of the algorithm. One particular problem I have is that it ...
2
votes
1answer
142 views

Voronoi diagram implementation using Delaunay Triangulation

I am trying to implement Voronoi diagram using Delaunay Triangulation as the dual of Delaunay Triangulation is Voronoi diagram. I have a little bit confusion about the time complexity of it ...
2
votes
0answers
112 views

Trying to re-create the Voronoi diagram as mentioned in the paper

I am trying to re-create the (center) Polyhedrons (or voronoi cells) that are mentioned in this paper (page 6). The following is $2$-dimention representation, I am trying re-create it in arbitary ...
1
vote
0answers
123 views

Ω($n^2$) intersections between the edges of the Voronoi diagram and the farthest site Voronoi diagram.

I'm working through Mark DeBerg's Computational Geometry book and I'm stuck on question 7.16 which states the following: Show that for some set P of n points, there can be Ω($n^2$) intersections ...
1
vote
0answers
171 views

Extension of Planar Algorithms to Higher-Dimensional Voronoi Diagrams

Voronoi diagrams are not new, and there are many established algorithms (Fortune's, Lloyd's) for generating them (or their duals, the Delaunay triangulation). There are many recent-ish papers too, ...
0
votes
1answer
79 views

Obtain the set of points from Voronoi diagram

Given a planar infinite two dimensional mesh graph such that each small polygon of the mesh is convex, is it correct to assume for any such mesh there exists a set of points such that the these ...
0
votes
1answer
96 views

Voronoi edges example

I have 4 line segments: 0 0 2 0 // 1st line segment 2 0 2 1 // 2nd line segment 2 1 0 1 0 1 0 0 and I wrote some CGAL code to print the Voronoi edges. However, <...
3
votes
0answers
64 views

Bounds on the size of Voronoi cells

I am working on an algorithm for which bounds on the size of voronoi cells will come in handy. Suppose that the domain $D$ is partitioned according to the Voronoi cells $D_1,\dots,D_n$ with Voronoi ...
1
vote
1answer
105 views

Prove that for any n > 3 there is a set of n point sites in the plane such that one of the cells of Voronoi diagram(P) has n − 1 vertices

I am trying to solve some exercises of the book "Computational Geometry Algorithm and Applications, 3rd - de berg et al" of chapter 7 - Voronoi Diagrams. Unfortunately, I am not sure if I understand ...
4
votes
0answers
220 views

Largest empty circle/sphere with non-polygonal location constraints

Finding Largest Empty Circles with Location Constraints contains the following theorem relating to the Largest Empty Sphere problem in 2-dimensions: Given a set S of n points and a k-gon P, the ...
1
vote
0answers
46 views

maximizing an objective function(area) with respect to location of a node

Consider two circles with radius R (They may intersect each other). We present circles by $C_A$ and $C_B$. We have additional node called $C$. We obtain Voronoi polygons with respect to center of each ...
3
votes
0answers
195 views

Are the vertices of a Voronoi diagram obtained from a Sierpinski attractor also a kind of attractor?

Trying to understand how the Voronoi Diagrams work I did a test generating the Voronoi diagram of the points obtained from The Chaos Game algorithm when it is applied to a $3$-gon. The result is a set ...
3
votes
1answer
290 views

How to triangulate from a Voronoï diagram?

I computed a Voronoï diagram from a set of point (with Boost.polygon). I try to find a Delaunay triangulation, connecting each cell center for each Voronoï edge, but I miss some edges. In the ...
1
vote
0answers
52 views

Algorithm detect simple curves using Voronoi diagram or Delaunay triangulation?

I wonder if there is algorithm/method to determine if closed (or even non closed) curve is simple or not, using the mathematics from the field of computational geometry? Especially I wonder if exist ...
1
vote
0answers
24 views

probabilistically segmenting a rectangle

I am trying to find ways to segment a image randomly, but drawn from a probalistic distribution of pre-determined areas to be cut through. First thought was to pick random points and run Covex hull ...
5
votes
0answers
72 views

Average shape of Voronoi cells in dimension $n\ge 2$?

A Poisson point proess of constant intensity in $\mathbb R^n$ has a Voronoi diagram. It is known that when $n=2$ the average number of edges of a cell is exactly $6$. Last I heard (but that was a ...
1
vote
2answers
567 views

How to compute convex hull of set points from Voronoi diagram in linear time

Given $n$ points in the plane and their Voronoi diagram, how do I prove that the convex hull of the points can be computed in linear time?
0
votes
2answers
144 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 ...