Honeycomb-type properties of the Delaunay triangulation and Voronoi diagram

2012-10-07T20:02:13Z

Suppose I'd like to distribute a set of points $P=\lbrace p_1 ,\dots, p_n \rbrace$ in the unit square $S=[0,1]\times[0,1]$ to minimize a weighted sum of two things:

1) The average distance between a uniformly selected point in $S$ and its nearest neighbor in $P$, i.e. $D_{avg}(P) = \iint_S \min_i\lbrace\|x-p_i\|\rbrace dA $ , and

2) The sum of the edge lengths in a Delaunay triangulation of $P$, notated $DT(P)$,

so that my problem can be written as

$\mathrm{minimize}_P ~ D_{avg}(P) +\phi DT(P)$

for some scalar $\phi$. Let's suppose that we can also choose the number of points in $P$ as well. My question is: as $\phi\rightarrow0$, is the optimal solution $P^*$ going to be a honeycomb lattice?

The honeycomb conjecture, http://en.wikipedia.org/wiki/Honeycomb_conjecture , would appear to suggest that the answer to my question would be "yes" if, instead of using a Delaunay triangulation, we took the sum of the edges of a Voronoi diagram of $P$, but even that will probably require quite a bit of work.

Honeycomb-type properties of the Delaunay triangulation and Voronoi diagram - MathOverflow

Honeycomb-type properties of the Delaunay triangulation and Voronoi diagram