1

I'd assumed that the minimal and maximal number of sides of a polygon in a Voronoi diagram were 3 and 6 and almost wrote that in the History of Science and Mathematics SE question Why doesn't John Snow's Voronoi diagram look like one? How was the diagram made? (distance to cholera-spreading water pump in 19th century London) but thought better of it.

For the internal polygons in a 2D diagram, (excluding the edges of a diagram for a finite number of points for example), what is the minimum and maximum possible number of polygon sides?

In the absence of a formal answer, are there at least cases where 2 or 7 are possible?

Assume:

$$r_{ij}=\sqrt{(x_i-x_j)^2 + (y_i-y_j)^2}$$

Tian Vlašić
  • 1,318
uhoh
  • 1,864

1 Answers1

3

For maximal; consider a case of n co-circular points lying on a circle of radius $1$. Let the $n$ co-circular points, along with the center of the circle; be the seeds of our Voronoi diagram.

We see the center points lead to a cyclic n-sided polynomial with a circumcircle of radius $1/2$. Since n can be arbitrarily chosen, so voronoi cell polygons can be arbitrarily $n$-sided.

For minimal; in general, bounded 2D voronoi cells in Euclidean space are polygons, so they should at least be a triangle. If we have equally spaced colinear points it leads to parallel lines - such might be taken as a case for n = 2.

Note that if we have even one non colinear point it would lead to a triangle.

uhoh
  • 1,864
Sagnik Chakraborty
  • 61