5
$\begingroup$

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:

enter image description here

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
$\endgroup$
  • 3
    $\begingroup$ In this setting, a cell is the set of all points that have the same set of second/third neighbors ? $\endgroup$ – Suresh Venkat Dec 16 '12 at 19:01
  • 3
    $\begingroup$ ...as opposed to the same ordered pair (second neighbor, third neighbor). $\endgroup$ – Jeffε Dec 17 '12 at 4:12

Your Answer

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

Browse other questions tagged or ask your own question.