Fitting a mesh to a density function - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T09:36:20Z http://mathoverflow.net/feeds/question/85624 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/85624/fitting-a-mesh-to-a-density-function Fitting a mesh to a density function John Gunnar Carlsson 2012-01-14T00:16:44Z 2012-01-14T20:35:30Z <p>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).</p> <p>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.</p> <p>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.</p> <p><img src="http://www.tc.umn.edu/~jcarlsso/triangular-lattice.jpg" alt="alt text"></p> http://mathoverflow.net/questions/85624/fitting-a-mesh-to-a-density-function/85633#85633 Answer by Dima Pasechnik for Fitting a mesh to a density function Dima Pasechnik 2012-01-14T04:33:06Z 2012-01-14T04:33:06Z <p>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. </p> http://mathoverflow.net/questions/85624/fitting-a-mesh-to-a-density-function/85688#85688 Answer by Anton Petrunin for Fitting a mesh to a density function Anton Petrunin 2012-01-14T20:35:30Z 2012-01-14T20:35:30Z <p>Here is one possible interpretation of your question.</p> <blockquote> <p>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$.</p> </blockquote> <p>(Say a triangle is $\varepsilon_n$-equilateral if the ratio of maximum side length and minimum side length is $\le 1+\varepsilon$.)</p> <p>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$.</p>