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
Improve this question
$\endgroup$
2
  • 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
    Commented Dec 16, 2012 at 19:01
  • 3
    $\begingroup$ ...as opposed to the same ordered pair (second neighbor, third neighbor). $\endgroup$
    – Jeffε
    Commented Dec 17, 2012 at 4:12

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.