That's an excellent observation. I was making the statement with large n in mind, but indeed for n=2,3,4 it is possible by the examples that you give. About n>4: The argument, that I give that n-1 is not possible, is that Euler's formula gives us that the number of edges is at most 3n-6 (and this only holds for n>2). For n=3,4,5,6... This means that we have at most 3,6,9,12,... edges. If we want every cell to have n-1 edges, then this means that we would have "n choose 2" = n * (n-1)/2 edges (where "/2" comes from the fact that every edge is shared by two cells). For n=3,4,5,6,... this is 3,6,10,15,.... Starting at 5, we have 3n-6 < n*(n-1)/2, therefore your list of examples is complete!

great to hear, thanks!

Happy to hear, thanks!

Thanks for your comment. I added a note in the video description that by relative interior I indeed mean the interior of the affine hull. It is always great to hear about applications of Voronoi diagrams (and Computational Geometry more generally). There are many variants of Voronoi diagrams, so there is probably already one that fits your purpose. The simplest way of weighing dimensions differently, is to simply scale the dimensions differently. I.e., if you "flatten" one of the dimensions, then it has less influence because the values are small anyway. Keep in mind that Voronoi diagrams only work well in small to medium dimension. Thus, if you have a high dimensional data set, you need to either reduce the dimension or use an appropriate alternatives. E.g. computing nearest neighbors (at least approximately) still works great in high dimensions.

Thanks! Yeah I thought about just scaling things that way, but I don’t have the actual data yet. There are only 3 dimensions to partition in the problem.

Sure. Let me say that I had bought the camera for vacation photos, before ever thinking of recording lectures at home. Looking back, it was a super lucky coincidence that I had this camera at hand when I needed it. Video: - Sony camera a6400 - Elgato Cam Link 4K - Elgato green screen (for a long time I just had a green sheet hanging behind me, but this is much nicer) - 2 no-name lighting soft boxes Audio: - Rode NT1-AI1 studio kit Video-recording: OBS Video-editing: Adobe premiere Writing on slides: Wacom One (I do prefer my Wacom Cintiq, but I only got that later and have it in the office). So in my hands you see in most videos the wacom pen and a logitech presenter. Slides: - ipe (ipe.otfried.org/) or powerpoint

@@algorithmslab Oh I didn't know Ipe could be used for presentations!

@@ianthehunter3532 All my Geometric Algorithms videos use Ipe slides. In the description of this video: kzfaq.info/get/bejne/rrJxeM6bq5u-qqc.html there is an example. Animations (in the sense of appear/disappear not move) can be done very nicely with views.

@@algorithmslab I will be sure to check those out, thanks!

Thanks for the feedback! Which equations are you referring to? Do you mean the equations at the end, i.e. starting at 20:32?

@@algorithmslab I found the equations at 10:44 onwards hard to understand :(

@@beanbean9019 Let me expand a bit on these equations here. Not sure how much it helps, but I think it fills in some details that might help. 1.) Voronoi cells: x is in V(p) if p is the closest site (i.e. point in P) to x. This can be expressed as saying that for every q in P (excluding p) that p is closer to x than q is to x. We know that these points are exactly the points in h(p,q). Since this should hold for all q in P (without p), x has to be in h(p,q) for all q, which is the same as saying that x has to be in the intersection of the halfspace h(p,q). Since we want to partition the whole space, we also need to consider all x that are in none of the cells, that is, x does not have a unique nearest neighbor in P. This leads us to Voronoi edges and vertices. First observe that since a Voronoi cell V(p) is the intersection of halfspaces, the boundary of a Voronoi cell (which is not part of the Voronoi cell) consists of pieces of boundaries of the halfspaces. The boundary of a halfspace h(p,p') is the bisector b(p,p'), thus the boundary of a Voronoi cell consists of pieces of bisectors. On the boundary of V(p) are exactly the points that have p as *a* nearest neighbor but not as the only nearest neighbor. The symbol that looks like a delta denotes the boundary. 2.) Voronoi edges: x is in the Voronoi edge V(p,p') if p and p' are both nearest neighbors of x, and x has no further nearest neighbors in P. From the discussion above it follows that x has to be on the boundary of V(p) (since p is a nearest neighbor of x) and x has to be on the boundary of V(p') (since p' is also a nearest neighbor of x). From the discussion above it also follows that this is part of the bisector b(p,p'), more specifically one continuous piece; therefore we get a (straight) edge (possibly going to infinity). But we have to be careful: Not every point that is on the boundary of V(p) and of V(p') is part of the Voronoi edge, because we only want to have those x that don't have another nearest neighbor. That is, to be part of a Voronoi edge x shouldn't be on more than two boundaries. But at the points where a Voronoi edge ends, this exactly happens (which is the reason that the edge ends there). Thus, for a Voronoi edge we want to exclude the endpoints (just as we excluded the boundary from the Voronoi cells). Describing it as the relative interior, is just of the intersection of boundaries, is just a different way for saying that we exclude the endpoints (en.wikipedia.org/wiki/Relative_interior) 3.) This leaves the Voronoi vertices: They have three or more nearest neighbors. As above this means that they are the intersection of three or more boundaries of Voronoi cells.

@@algorithmslab Thank you so much I get it! :D

The conquer game is commonly known as Voronoi game, and you will find various research papers and implementations for it online. The specific implementation I was talking about is the one we made as part of a set of games and puzzles called "ruler of the plane". You can find it here: kbuchin.github.io/ruler/ (to play: "play online" and then "conquer") and the sources here: github.com/kbuchin/ruler. It is a basic version of the game, i.e., just 1-on-1 without AIs.

OHh thank you for your quick answer ! @@algorithmslab

Instead of a video, let me simply reply to your comment; that's faster. The short answer, before delving into details, is that you might be looking for a kinetic data structure (KDS) for Delaunay triangulations. A good description for this gives Section 3.5 in the following PhD thesis: Russel, Daniel. Kinetic data structures in practice. Diss. Stanford University, 2007. But before using/implementing a general KDS, you should think about what you actually need. Just as an example: There is a nice applet VoroGlide in which the user can interact with the Voronoi diagram (VD)/Delaunay triangulation (DT) by dragging the sites. It works like a charm, but what it actually does, is simply recomputing the VD/DT from scratch all the time. This works since the point sets in the given interactive setting will be small. The lesson here is that it is good to think about what you actually need. Even if we want to avoid recomputing the complete DT/VD, if we know that only one point moves, there are much simpler solutions than a complete KDS. Before I start: You are asking about the VD, but I will reply in terms of the Delaunay triangulation. It is easier to handle/store and contains all the information that is needed for maintaining the VD. In particular, as long as the DT does not change combinatorially, we only need to update the positions of the Voronoi vertices. These are easy to compute by a standard formula for the center of a circumcircle. Lets for a moment go back to the setting, where only one point moves. Here we can make use of the fact that an edge is Delaunay if and only if it is legal. So after moving the point, we only need to check edges that this point might make illegal. Those are all edges of the triangles incident to the point. For each of these edges we can test whether they are still legal by an incircle test, which can be implemented robustly by reducing the problem to testing the sign of a certain determinant (see www.cs.cmu.edu/~quake/robust.html). Note that if we flip an edge, this might result in further edges that we need to check (as in the routing LegalizeEdge). Also note that in contrast to the case of point insertion, we also need to check the edges incident to the point. In any way, the case of one moving point is easy to handle. Now lets assume more points are moving over time. We now generalize what we did in the previous paragraph, but do it in a clever way. To determine which edge of the DT will flip first, we need to know more about the movement. Kinetic data structures commonly assume that the movement of the points can be described by a polynomial over time. For simplicity lets assume points move linearly of time t, i.e., the points are linear functions in t. Now we can do the following to determine which edge will flip next: For each edge of the DT, we can find the determinant for the incircle test; setting it to "== 0" and solving for t, will determine the point in time where the edge would flip. We can build a priority queue to see which edge would flip next, handle it etc. What else is to be said about this problem: 1. There is a video introduction to kinetic data structures but not for KDS for DT. Anyway, if you are interested, it's by Erik Demaine: ocw.mit.edu/courses/6-851-advanced-data-structures-spring-2012/resources/session-4-geometric-structures-ii/ (KDSs start at 00:31:22) 2. KDS for DT was part of CGAL up to version 4.11. The package was described in the PhD thesis mentioned above, and you can find the entry in the CGAL manual here: doc.cgal.org/4.11/Kinetic_data_structures/index.html But CGAL code might be a bit difficult to read if you are not used to generic programming with templates in C++. 3. The following is only of theoretical interest, and won't help you solve the problem: For long time it was an open problem how often the DT might change when the points move linearly. This problem was essentially resolved in the following article: Rubin, Natan. "On kinetic Delaunay triangulations: A near-quadratic bound for unit speed motions." Journal of the ACM (JACM) 62.3 (2015): 1-85. I hope this answers your question.

​@@algorithmslab So, the question of what i've actually want to do/need came up - during my PhD i worked a lot with molecular dynamics simulations of proteins (I'm a molecular biologist/bioinformatician). Those mostly use spherical potentials/point charges. For example, one usually approximates water with 3 or 4 point charges with spherical electrostatic potentials. I've came by Voronoi diagrams completely by accident and came up with an idea which since became kind of a hobby project - do an MD simulation with Voronoi cells being kind of bubbles - ie, they exert pressure on neighbouring cells depending on how much volume they have at the moment - the smaller the bubble, the more pressure it exerts. There are multiple things one could do with such a construct, but what i then would like to do is to overlay a discrete, or 'finite element' field over it - be able to associate a scalar or a vector value with each bubble, interacting with the neighbours. By necessity this means that ALL central points of the voronoi cells move at each time step. Recomputing the entire diagram would be possible I guess, but super costly. One interesting thing i've managed to find is a series of papers from Asia, where author, among other things, created an alternative to sweepline - an 'untransformed sweep circle' - which was easier to parallelize (doi:dx.doi.org/10.1016/j.cad.2012.10.031 Xin et al 2013). Note that this is different to 'sweepcircle' from Dehne and Klein 1987. I've seen also people tried to chip around the problem by reducing the amount of edges which need to be checked if they need to be flipped/splitted/merged (for e.g. zhou et al 2010). There is also i guess promising but unpublished article by Hugo Ledoux from Delft "The Kinetic 3D Voronoi Diagram: A Tool for Simulating Environmental Processes" and 2014 IEEE publication by Peterka et al "High-Performance Computation of Distributed-Memory Parallel 3D Voronoi and Delaunay Tessellation". Note that i am mixing 2D and 3D works because my plan was to get the thing working in 2D first (which seems simpler) and then move to 3D. One step at a time strategy : ) I kind of hoped that having the derivatives of positions of central points i could derive the positions of the voronoi vertices directly : ( The biggest obstacle however is, i can get the general idea behind those works, but trying to implement them myself requires intimate understanding of the details and this is a huge obstacle due to my wet lab molecular biologist background and dyslexia which causes my brain to have much harder time parsing abstract symbols. Thanks for the extensive answer. It definitely is a bit of a step forward for me. I was aware of the Rubin and Natan paper, but didnt know about older versions of CGAL and the video, so I will definitely check it out. Btw I am an experienced Fortran/C/C++ programmer (I work in the airline industry at the moment on flight path optimization) so if you ever need a piece of code written, let me know. I miss the creative part of the academic work :D Your videos are a goldmine so please keep up the good work!

@@empireempire3545 Hugo Ledoux's paper is work that he did during his PhD (3d.bk.tudelft.nl/hledoux/phdthesis/), and he has made the code available as it is (3d.bk.tudelft.nl/courses/geo1004/data/hugotetra.zip). The corresponding code is in Mesh.pas. Note that this is based on moving one point, "MovePointTo". It is based on the same ideas that I outlined in my reply above: The idea is to first find out what the next topological event is (i.e., a combinatorial change to the VD/DT) and to move "the point" that causes it. Btw., the code is made available with a lesson on 3d Voronoi diagrams (3d.bk.tudelft.nl/courses/geo1004/), which includes a video (kzfaq.info/get/bejne/pbV3q5yBuq3GZZc.html). I don't know the other work that you mention. Obviously, parallelization is a good idea in this setting, because most computations are local. I haven't tried the maths to determine the centers of the spheres by the derivatives of the sites, but for the general structure of the code, this won't make a difference. "Chip around the problem by reducing the amount of edges which need to be checked" sounds very reasonable, and you also effectively do this when using Kinetic Data Structures. Repeatly calling a sweepline algorithm sounds like too much work. Personally, I would also always use a randomized incremental construction in dimensions 3 and higher. Sounds like a great project. Good luck with it!