Say I have a Voronoi diagram of some points $p_1,\dots,p_n\in\mathbb{R}^d$, which tesselates $\mathbb{R}^d$ into cells $V_1,\dots,V_n$. Within each cell $V_i$, the pole is defined as the vertex of $V_i$ that maximizes the distance to the landmark point $p_i$, i.e. $\arg\max_{x\in V_i} \|x-p_i\|$. Is there an efficient algorithm for computing these poles? It seems that this is well-studied in $d=2$ but I cannot find any literature on other cases.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Voronoi diagram $\endgroup$– Alex DegtyarevMar 17, 2015 at 7:13
-
1$\begingroup$ Why the downvote? $\endgroup$– Victor TuMar 17, 2015 at 7:21
-
2$\begingroup$ It would seem to be difficult to improve upon: Compute the Voronoi diagram, compute the distances of the vertices from the sites, take the max. Is there a faster algorithm in $\mathbb{R}2$ ? $\endgroup$– Joseph O'RourkeMar 17, 2015 at 11:23
-
1$\begingroup$ For each cell, you seem to need to maximize a convex quadratic function on it. This surely cannot be easy in general. $\endgroup$– Dima PasechnikMar 17, 2015 at 11:37
Add a comment
|