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.
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$– Benoît KloecknerCommented 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$– Benoît KloecknerCommented Mar 27, 2015 at 10:05
Add a comment
|