Questions tagged [voronoi-diagrams]
The voronoi-diagrams tag has no usage guidance.
24
questions
1
vote
0
answers
22
views
Matching a 2D points cloud to polylines
I have a (2D) point cloud of reasonable size (say some thousands of points) and a set of (2D) polylines also of a reasonable size. I want to assess the discrepancies between the two geometries and for ...
user16034
2
votes
1
answer
52
views
Is Fortune's algorithms for Voronoi diagrams described anywhere by Prof. Fortune?
One popular algorithm to find the Voronoi diagram out of a collection of points (sites) in the plane is Fortune's algorithm. It is usually described in terms of a sweep line, whose interaction with ...
- 123
2
votes
2
answers
156
views
Algorithm for farthest point Voronoi diagram?
I am looking for an algorithm to compute the furthest point Voronoi diagram and I don't seem to be able to find anything decent. The most complete one I have found are these slides and this terribly ...
- 291
6
votes
2
answers
277
views
What edges are not in a Gabriel graph, yet in a Delauney graph?
It is know that the Gabriel graph of a point set $P \subset \mathbb{R}^2$, $\mathcal{GG}(P)$ is a subset of the corresponding Delauney graph $\mathcal{DG}(P)$, i.e. $\mathcal{GG}(P) \subseteq\mathcal{...
- 123
0
votes
1
answer
77
views
Nearest Neighbour search with Kirkpatrick's Hierarchy and Re-Triangulating Delaunay after vertex removal
Ok, so I'm having bit of an issue understanding nearest neighbour search with delaunay triangulation.
In particular, how do I re-triangulate my delaunay triangulations once I introduced holes?
But I ...
- 103
1
vote
0
answers
64
views
Transition from Delaunay triangulation to Voronoi diagram
In mathematics and computational geometry, a Delaunay triangulation for a given set P of discrete points in a plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any ...
- 11
2
votes
0
answers
151
views
"Loneliest point" algorithm
Problem:
I'm looking for an algorithm to find the maximal Euclidean distance between points in a set $R$ and another set $S \subseteq R$.
Specifically, given a finite set of points $S$ in $n$-...
7
votes
2
answers
197
views
Voronoi Diagram Drawing Variations and Charateristics
I am learning about Voronoi diagrams and I have seen that the Voronoi diagram of a set of points is drawn with straight line segments and rays.
Similarly how can we draw the Voronoi diagram for the ...
6
votes
1
answer
166
views
Voronoi Cell and Voronoi Diagram
Consider a set R of n red points and B of n blue points in the plane. Let x∈R and y∈B be the shortest edge xy. Let P = R ∪ B. Let Vor(P) be the Voronoi diagram of P. Let V(x) be the Voronoi cell of x ...
- 117
6
votes
0
answers
117
views
Placing a tripod in a plane such that it partition a given set of points (with pic)
I would appreciate if anyone could help me with the following problem:
Given a set of 3n points in the plane with n > 0, is it possible to find a placement of a tripod such that each region contains ...
- 141
3
votes
1
answer
194
views
Can breakpoints of the beachline move up in Fortune's algorithm?
In these slides describing Fortune's algorithm for constructing a Voronoi diagram, it is noted on page 7 that break points of the beach line can move upward. How is this so?
In most of the cases I ...
- 131
2
votes
1
answer
133
views
Delaunay to Voronoi ... and back?
Learning about Voronoi Diagrams, one quickly finds out that Delaunay Triangulations are clearly the easiest way to generate them from a set of points.
How about the other way around? Given a ...
- 21
1
vote
1
answer
49
views
Robot swarm, Maximum area coverage
I have a swarm ofN robots to place on a plane area. Each robot would control a sub part of the area (navigating in it). What algorithm could I use to deploy my ...
- 11
3
votes
1
answer
213
views
Is every planar graph a possible dual graph of a voronoi diagram?
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 ...
- 131
1
vote
1
answer
2k
views
Finding the Voronoi cell a point belongs to
Given a set of Voronoi edges. Each edge consists of (indices of, pointers to) 4 points: $\mathrm{left}$ and $\mathrm{right}$ are sites, $\mathrm{begin}$ and $\mathrm{end}$ are vertices (one of them or ...
- 165
2
votes
2
answers
102
views
Compare two atan2
I tried to implement points location algorithm using Fortune's algorithm to get Voronoi diagram and another sweepline algorithm to locate many points in $O(n\cdot\log(n))$. If there are multiple ...
- 165
1
vote
0
answers
564
views
Voronoi diagram neighbors
I'm trying to find all the neighbors of a given cell in a voronoi diagram.
For example, given the following diagram, if I want to find the neighbors of the cell 1, then I should be able to return the ...
- 33
0
votes
0
answers
73
views
Voronoi diagram of a set of simple polygons
The Voronoi diagram is a well-known data structure that helps solve various proximity problems. We have several nice algorithms that build this diagram for $n$ point in optimal time $O(n\log n)$.
I ...
user16034
4
votes
0
answers
70
views
Repeated nearest-neighbor queries
If I want to make N repeated (i.e. millions of) 2D nearest-neighbor queries on a pointset of size M, is traveling down into a KD-Tree most efficient or are there better ways to do this? (e.g. Voronoi?)...
- 141
6
votes
0
answers
1k
views
Voronoi diagram. Status structure in Fortune's Algorithm
I'm trying to implement the Fortune's Algorithm, however I can't quite figure out how the status structure should be implemented.
The following is extrapolated from my Computational Geometry book.
...
- 693
2
votes
0
answers
94
views
What is the runtime to compute the ordered higher-order Voronoi diagram?
The ordered order-k Voronoi diagram (sometimes written OOKVD) partitions the plane into regions such that the k closest sites are the same and in the same order for all the points in a region.
I am ...
1
vote
1
answer
627
views
Finding the nearest neighbour of an existing 2d point in a set of points within $\mathcal{O}(\log{}n)$ time
Question
Is it possible to find an existing point's nearest neighbour within a logarithmic upper bound?
What I've tried
I have:
the set of points $P$,
a point $p$, where $p\in P$,
a point $q$, ...
- 111
0
votes
1
answer
477
views
Voronoi Diagram: Exactly 2n-5 vertices
I want to find some characteristics for a set of points $S$ which contains $n$ points and has some Voronoi Diagram $V(S)$. This diagram should have exactly $2n-5$ vertices.
I tried to use the Euler ...
- 269
1
vote
0
answers
200
views
Voronoi Diagram Question
I am stuck on that question, it's about Voronoi diagrams
Show that for some set of $n$ points, there can be $\Omega(n^2)$ intersections
between the edges of the Voronoi diagram and the edges of ...
- 129