10
$\begingroup$

Suppose I have a probability density function defined on a region in the plane (in my case, the pdf is of the form $f(x) = \alpha\|x\|^{-\beta}$, and the region is the unit disk). For large $N$, is it possible to place $N$ points $X_1,\dots,X_N$ in the region so that the points $X_i$ are distributed according to $f(x)$, and also form a mesh of (approximately) equilateral triangles? This is clearly trivial when $f(x)$ is uniform (just put the $X_i$ in a uniform triangular lattice).

For the non-uniform case, obviously some triangles will be larger than others, but I want each individual triangle to be approximately equilateral (e.g. maximum side length and minimum side length are within 1% of each other, etc.). One possibility for the non-uniform case would be to sample $N$ points independently at random from $f(x)$ and then take their Delaunay triangulation, but I don't think there is a guarantee that the triangles will be roughly equilateral (i.e. some will be long and skinny) as $N$ becomes large.

The picture below is along these lines, if you ignore the big ugly hole in the center; each triangle is roughly equilateral, but points are not uniformly distributed.

    alt text (source: Wayback Machine)

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

Here is one possible interpretation of your question.

Assume a probability density function $f$ is given. Is there a sequence of triangulations $T_n$ with $\varepsilon_n$-equilateral triangles such that counting probability measure on nodes converges to $f$ and $\varepsilon_n\to 0$ as $n\to\infty$.

(Say a triangle is $\varepsilon_n$-equilateral if the ratio of maximum side length and minimum side length is $\le 1+\varepsilon$.)

I am almost sure that the answer is "YES" if and only if $f$ is conformal factor of a flat metric; i.e., if and only if $f=e^{2{\cdot}\phi}$ and $\Delta \phi\equiv 0$.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Thanks a lot, Anton -- I hadn't made the connection to conformal maps, but that's clearly the right way to think about things. I gather that, in my particular case with $f(x) = \alpha\|x\|^{-\beta}$ on the unit disk, the answer is therefore no? $\endgroup$
    – John Gunnar Carlsson
    Jan 15, 2012 at 2:40
  • 2
    $\begingroup$ @John: Sorry my last comment was not correct, so I delete it. My answer is OK in the case if $f$ has no zeros and the domain is simply connected. In particular $f=\alpha{\cdot}|x|^{-\beta}$ is OK once the domain is simply connected. $$ $$ If the domain is not simply connected then in addition the holonomy group should be $\mathbb{Z}_6$ in $\mathbb S^1$. For example $f=|x|^{-2/7}$ should be OK for the annulus (I might make a mistake). (Constructing a triangulation near zero of $f$ seems to be impossible, so you need to cut it from your domain.) $\endgroup$
    – Anton Petrunin
    Jan 15, 2012 at 6:25
  • 1
    $\begingroup$ Ah, interesting; many thanks for the follow-up. When you say "$f=\alpha{\cdot}|x|^{-\beta}$ is OK once the domain is simply connected", do you mean that such a triangulation DOES NOT exist for this case (I inferred this from your next example with $|x|^{-2/7}$ on an annulus)? Also, did the $-2/7$ come from anywhere in particular, or would, say, $-2/3$ work as well? (I will admit that I do not know what a holonomy group is, and clearly have quite a bit of reading to do) $\endgroup$
    – John Gunnar Carlsson
    Jan 15, 2012 at 9:05
  • 2
    $\begingroup$ Take a cone $C_n$ with angle $n{\cdot}\tfrac\pi3$. (We need angle proportional to $\tfrac\pi3$ so $C_n$ admits a triangulation in equilateral triangles) The map $C_n\to \mathbb C$, defined as $z\mapsto z^{6/n}$ is conformal. The conformal factor is proportional to $(|z|^{6/n-1})^2$. So any $\beta= 2-12/n$ will do. (Sorry if I made a mistake in calculations.) $\endgroup$
    – Anton Petrunin
    Jan 15, 2012 at 18:20
3
$\begingroup$

There is an analogy in mechanics that might help: think of the nodes of the mesh as being connected by springs, which have tension proportional to something meaningful, e.g. the integral of $f(x)$ along the segment $[X_i,X_j]$. Then, if you let it stabilize, you will get a mesh with nodes distributed roughly according to $f$; if you pre-process $f$ to make is smooth enough so that it does not change much on every initial triangle, you should end up with roughly equilateral triangles, too.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.