MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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, , 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.

share|cite|improve this question
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$. – Yoav Kallus Oct 7 '12 at 21:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.