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
    Commented 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
    Commented 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
    Commented 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
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .