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.

  • $\begingroup$ A similar problem to yours for $\phi=0$ is the quantizer problem, where the distance is squared. If the triangular lattice is the unique optimal arrangement for the case $\phi=0$ it should also be optimal in the limit $\phi\to 0$. $\endgroup$ – Yoav Kallus Oct 7 '12 at 21:45

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.