# Computing Voronoi poles in $\mathbb{R}^d$ (the farthest points within each cell)

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.

• Voronoi diagram – Alex Degtyarev Mar 17 '15 at 7:13
• Why the downvote? – Victor Tu Mar 17 '15 at 7:21
• 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$ ? – Joseph O'Rourke Mar 17 '15 at 11:23
• For each cell, you seem to need to maximize a convex quadratic function on it. This surely cannot be easy in general. – Dima Pasechnik Mar 17 '15 at 11:37