# Questions tagged [voronoi-diagrams]

The tag has no usage guidance.

9 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
593 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. ...
59 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?)...
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$-...
68 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 ...
75 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 ...
373 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 ...
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 ...
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 ...