Questions tagged [voronoi]
The voronoi tag has no usage guidance.
7
questions
5
votes
0
answers
92
views
Optimal point placement on integer lattice
What is known about the following point placement problem?
For positive integers $N$, $n<N^2$, and $N\times N$ grid $\mathcal{G}$, compute
\begin{eqnarray*}
\mu_1(N,n)\triangleq\min_{\mathcal{P}\...
- 51
-1
votes
1
answer
341
views
Example of Delaunay Triangulation where it does not minimize the maximum angle
I know that that the Delaunay triangulation maximizes the minimum angle of triangulation.
And it does not minimize the maximum angle. If we consider the set of points in general position(no four ...
- 1,531
4
votes
0
answers
291
views
Voronoi diagram in presence of polygonal obstacle
Suppose there is a set of convex polygons ($\mathbb{P}$) on the plane. For each convex polygon $P_i$ there is one "facility" $f_i$ placed on the boundary of $P_i$.
The distance between a point $p \in ...
- 1,006
2
votes
1
answer
135
views
Weighted furthest point voronoi diagrams
I found that Weighted nearest neighbor voronoi diagrams are widely studied and there are optimal algorithms for that.
But I could not find anything on Weighted furthest point voronoi diagrams !! But ...
- 1,006
3
votes
0
answers
57
views
Voronoi diagrams applications where the input order has some known properties?
Are there applications of Voronoi diagrams or Delaunay triangulations where the order in which the points are generated (and given to the algorithm) have some known properties (e.g. concatenation of ...
- 2,733
3
votes
1
answer
217
views
Outer part of Voronoi diagram in 3D
Given a set of points $V \subset \mathbb{R}^d$, the Voronoi diagram divides $\mathbb{R}^d$ into $|V|$ parts such that for every $v \in V$, the part of $\mathbb{R}^d$ for which $v$ is closer than any ...
- 4,670
8
votes
1
answer
347
views
Sampling from the Voronoi cell of a point
Fix a set of $n$ points $P \subset \mathbb{R}^d$. Now a query point
$q$ arrives, and the goal is produce a point $r$ sampled uniformly
at random from the Voronoi cell of $q$ in the set $P \cup \{q\...
- 32k