Honeycomb-type properties of the Delaunay triangulation and Voronoi diagram - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T14:48:37Z http://mathoverflow.net/feeds/question/109096 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109096/honeycomb-type-properties-of-the-delaunay-triangulation-and-voronoi-diagram Honeycomb-type properties of the Delaunay triangulation and Voronoi diagram John Gunnar Carlsson 2012-10-07T20:02:13Z 2012-10-07T20:02:13Z <p>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:</p> <p>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</p> <p>2) The sum of the edge lengths in a Delaunay triangulation of $P$, notated $DT(P)$,</p> <p>so that my problem can be written as</p> <p><code>$\mathrm{minimize}_P ~ D_{avg}(P) +\phi DT(P)$</code></p> <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?</p> <p>The honeycomb conjecture, <a href="http://en.wikipedia.org/wiki/Honeycomb_conjecture" rel="nofollow">http://en.wikipedia.org/wiki/Honeycomb_conjecture</a> , 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.</p>