Questions tagged [voronoi]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
5 votes
0 answers

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}\...
user56067's user avatar
-1 votes
1 answer

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 ...
Inuyasha Yagami's user avatar
4 votes
0 answers

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 ...
Dibyayan's user avatar
  • 1,006
2 votes
1 answer

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 ...
Dibyayan's user avatar
  • 1,006
3 votes
0 answers

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 ...
J..y B..y's user avatar
  • 2,733
3 votes
1 answer

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 ...
Alex ten Brink's user avatar
8 votes
1 answer

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\...
Suresh Venkat's user avatar