1
$\begingroup$

Say that $x_1,\dots,x_n$ are points in the plane, with a Voronoi diagram $V_1,\dots,V_n$. The Voronoi diagram is typically defined by $$V_i = \{x:\|x-x_i\|\leq \|x-x_j\|~\forall j\}~.$$ Is there any concise way to define a Voronoi diagram so that the boundary components are uniquely assigned to pieces $V_i$? That is, so that each point $x$ belongs to exactly one Voronoi component? (the definition I gave above assigns points on the boundary to multiple cells) A lexicographic ordering would work, but it seems messy to write out.

$\endgroup$
2
  • 1
    $\begingroup$ I don't see the problem with the ordering idea. Either define $V_i$ by induction, adding the assumption that $x\notin V_j$ for all $j<i$ in the definition of $V_i$ ; or define $i(x)$ as the $i$ in $\{1,\dots,n\}$ such that $|| x-x_i ||\le || x-x_j ||$ for all $j$, and let $V_i=\{x : i(x)=i\}$. $\endgroup$ Mar 27, 2015 at 10:03
  • 1
    $\begingroup$ These method has the inconvenient of breaking the symmetry of the numbering though; you can decide to break ties by choosing the $i$ such that $x_i$ has least first coordinate, then the least second coordinates. This might be what you meant by lexicographic ordering, but it should be no trouble to define $i(x)$ as above with the current tie breaker. $\endgroup$ Mar 27, 2015 at 10:05

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.