3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Voronoi diagram $\endgroup$ – Alex Degtyarev Mar 17 '15 at 7:13
  • 1
    $\begingroup$ Why the downvote? $\endgroup$ – Victor Tu Mar 17 '15 at 7:21
  • 1
    $\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'Rourke Mar 17 '15 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 Pasechnik Mar 17 '15 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.