Questions tagged [voronoi-diagrams]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
6
votes
2answers
76 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
1answer
107 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 ...
6
votes
0answers
104 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 ...
6
votes
0answers
613 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. ...
4
votes
0answers
61 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?)...
3
votes
1answer
117 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 ...
2
votes
2answers
61 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 ...
2
votes
1answer
68 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 ...
2
votes
0answers
111 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$-...
2
votes
0answers
70 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 ...
2
votes
0answers
76 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
1answer
37 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 ...
1
vote
1answer
1k 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 ...
1
vote
1answer
565 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$, ...
1
vote
0answers
380 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 ...
1
vote
0answers
173 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 ...
0
votes
1answer
356 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 ...
0
votes
0answers
57 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 ...