1
$\begingroup$

I'm a programmer trying to implement a graphical effect using 2D Voronoi diagrams, and I'm wondering what kind of basic geometric transformations I can apply to it while having it still remain a valid Voronoi diagram.

Intuitively, I think I should be able to translate, rotate, reflect and scale it, as long as the scale is uniform along both axes. I can't scale it non-uniformely or shear it. Is that correct?

$\endgroup$

closed as off-topic by Dima Pasechnik, Stefan Kohl, YCor, Alex Degtyarev, Ben Barber Nov 7 '17 at 21:09

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Dima Pasechnik, Stefan Kohl, YCor, Alex Degtyarev, Ben Barber
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ that's right; basically you need to preserve the distances between points on the plane (or scale them uniformly). $\endgroup$ – Dima Pasechnik Nov 7 '17 at 12:42
  • $\begingroup$ Right, of course, that criterion makes perfect sense. Thanks! $\endgroup$ – Oskar Nov 7 '17 at 12:48
  • 1
    $\begingroup$ I don't know what Voronoi diagrams are, but Dima's comment makes me think that your transformations should be from the group ${\mathbb R}^2\rtimes ({\rm O}(2)\times {\mathbb R}^*)$, i.e. all transformations should be a product $T.R.S$ where $T$ is a translation, $R$ is a rotation/reflection, and $S$ is a scalar matrix. $\endgroup$ – Nick Gill Nov 7 '17 at 17:27
  • 1
    $\begingroup$ This question does not appear off-topic. Perhaps the preamble "I'm a programmer..." led some to this conclusion. The question can be understood in one of two senses. (a) Under what transformations of a set of points and their Voronoi diagram does the transformed VD remain the VD for the transformed set of points? (b) Under what transformations does a VD remain a VD for some, possibly different, set of points. It's not obvious to me that the answers to these question must be the same. $\endgroup$ – Menachem Nov 8 '17 at 15:13
  • 1
    $\begingroup$ There are certainly (somewhat generic) cases in which non-uniform scaling transforms a point set and its VD in a consistent manner. For example, Z^n and its VD can be scaled non-uniformly in orthogonal directions and remain consistent. Another interesting question (though probably not @Oskar's question) might consider which transformations preserve the VD's combinatorial structure. This does not seem obvious to me, even for the simple case of a lattice. If answers to these questions are already known, perhaps the question can be considered merely asking for a reference. $\endgroup$ – Menachem Nov 8 '17 at 15:14