Stack Exchange Network

Stack Exchange network consists of 174 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
0answers
24 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
40 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
22 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
55 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
179 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
57 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
50 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
11 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
109 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
104 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
229 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
57 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
240 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
247 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
254 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
217 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
125 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
115 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
138 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
101 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
117 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
151 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
75 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
88 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
62 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
94 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 ...
3
votes
0answers
205 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
191 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
286 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
51 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
69 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
547 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
133 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 ...