<p>Where order-$k$ Voronoi diagrams partition according to the $k$ closest sites
(<a href="http://books.google.com/books?isbn=3540779736" rel="nofollow noreferrer">de Berg et al.</a>
p. 169),
consider partitioning on the 2nd and 3rd closest &mdash;
call these [2,3]-Voronoi partitions.<br>
Each cell is tagged with a set (unordered) of 2 sites $\{ p_i, p_j \}$.<br>
Some pictures with Nsite = 5 random sites in the plane:</p>

<p><img src="https://i.sstatic.net/caTz6.png" alt="enter image description here"></p>

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

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

<pre><code>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
</code></pre>

CC BY-SA 3.0
2012-12-16T19:01:55.640Z
In this setting, a cell is the set of all points that have the same **set** of second/third neighbors ?
Suresh Venkat
CC BY-SA 3.0
2012-12-17T04:12:28.760Z
...as opposed to the same **ordered pair** (second neighbor, third neighbor).
Jeffε
<cg.comp-geom>
Voronoi partitioning on the 2nd and 3rd closest: how many pieces?
Denis
# Voronoi partitioning on the 2nd and 3rd closest: how many pieces?

(Asked by: username_0 on 2012-12-16)

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

**Tags:** cg.comp-geom

> **Comments:**
> **username_1**: In this setting, a cell is the set of all points that have the same **set** of second/third neighbors ?  
> **username_2**: ...as opposed to the same **ordered pair** (second neighbor, third neighbor).  

---

## 0 answers

