# Voronoi partitioning on the 2nd and 3rd closest: how many pieces?

Where order-$k$ Voronoi diagrams partition according to the $k$ closest sites (de Berg et al. p. 169), consider partitioning on the 2nd and 3rd closest — call these [2,3]-Voronoi partitions.
Each cell is tagged with a set (unordered) of 2 sites $\{ p_i, p_j \}$.
Some pictures with Nsite = 5 random sites in the plane:

How does the number of cells in a [2,3]-Voronoi diagram vary with Nsite
and dimension $d$ in $\mathbb{R}^d$ ?

Added 18 Dec: some numbers from Monte Carlo
(despite "avoid experiment not backed up by a little theory"):

1-2-Voronoi 2d  3d  4d
----------------------
nsite  5:    7   9   9
nsite 10:   20  29  40
nsite 20:   44  79 139

2-3-Voronoi 2d  3d  4d
----------------------
nsite  5:   15  28  28
nsite 10:   57 129 246
nsite 20:  136 359 740

• In this setting, a cell is the set of all points that have the same set of second/third neighbors ? Commented Dec 16, 2012 at 19:01
• ...as opposed to the same ordered pair (second neighbor, third neighbor). Commented Dec 17, 2012 at 4:12