5
$\begingroup$

Let $P_i$ be a set of points in the plane and $P_{i+1}$ the corners of the Voronoi diagram of $P_i$. Start with some $P_1$ and iterate away. What happens? Can you choose a $P_1$ so the iteration goes into a stable loop? (If you play the game on a torus, $P_1=${some point} works, on a sphere $P_1=${a tetrahedron} works either.) It's relatively easy to see that if $P_i$ has exactly two inner points, $card[P_{i+1}]=card[P_i]$, but this is neither necessary nor sufficient - nothing tells you how many inner points $P_{i+1}$ has.

$\endgroup$
  • $\begingroup$ I think whenever you have a lattice you will have lattice, you get such a loop. But can you find a finite set where $|P_{i+1}| \geq |P_i|$? $\endgroup$ – flawr Jan 21 '18 at 20:52
  • 1
    $\begingroup$ @flawr The Voronoi diagram of the seven points $\{(0, 0), (4, 0), (0, 4), (4, 4), (2, 2), (3, 2), (1, 2)\}$ has eight vertices. $\endgroup$ – Martin Ender Jan 21 '18 at 23:31
  • $\begingroup$ Related question (not fully answered): "Does this iterated Delaunay triangulation process always “explode”?" $\endgroup$ – Joseph O'Rourke Jan 22 '18 at 2:07
  • $\begingroup$ Surplus conjecture: Let P be set of all six point sets that are symmetric to the origin and have two interior points. It looks like vor(p) is in P whenever p is, but I yet have no idea about what happens to the distances in the long run. $\endgroup$ – Hauke Reddmann Jan 27 '18 at 20:19
2
$\begingroup$

Not answering your questions, but here are five iterations starting with $10$ random points:


          VorIter5
          In the first frame, the $10$ points are clustered in the large central dot.
          Subsequent frames alternate Voronoi sites (orange) and Voronoi vertices (blue).
And here is the last frame enlarged:
          5thFrame
          Enlarged view of 5th frame in sequence above.
          In the next, 6th frame, the blue points would become the orange Voronoi sites.
It appears to me, from limited empirical exploration, that, for random points uniformly distributed in a square, the number of points $|P_{i+1}|$ is very roughly $1.8 |P_{i}|$ with each iteration. So growing from $10$ points to ${\sim}100$ points after $4$ iterations.

$\endgroup$
1
$\begingroup$

In a Euclidean space, the set $P_{i+1}$ is contained in the interior of the convex hull of $P_i$. Thus the convex hull of $P_{i+1}$ is a proper subset of the convex hull of $P_i$, and there can be no cycle.

EDIT: no, sorry, this is false. If $P_i$ are the vertices of an obtuse-angled triangle, then the (only) Voronoi vertex is the circumcenter which lies outside of the triangle. Still, I hope that there is some kind of "monotonicity" that prevents a cycle...

$\endgroup$
  • $\begingroup$ Did you reverse the inclusions? The Voronoi vertices extend beyond the hull of the sites. (Your point remains.) $\endgroup$ – Joseph O'Rourke May 19 '18 at 11:03
  • 1
    $\begingroup$ Actually, neither inclusion holds in general. Take the vertices of a triangle as the starting set. There is only one Voronoi vertex: the circumcenter. Now it depend on whether the triangle is acute-angled or not... I have edited my answer. $\endgroup$ – Ivan Izmestiev May 19 '18 at 11:56

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.