User john gunnar carlsson - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T07:22:04Z http://mathoverflow.net/feeds/user/11828 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/130104/boundary-surfaces-in-a-3d-voronoi-tessellation-with-obstacles Boundary surfaces in a 3d Voronoi tessellation with obstacles John Gunnar Carlsson 2013-05-08T18:07:49Z 2013-05-08T18:07:49Z <p>Let $x_1,\dots,x_n$ be a set of points in $\mathbb{R}^3$ and let $\mathcal{O}_1 ,\dots, \mathcal{O}_m$ denote a set of polyhedral obstacles. What is the name for the surfaces that describe the boundaries of a Voronoi tessellation of $\mathbb{R}^3$ with respect to the points $x_i$, using the shortest-path metric induced by the obstacles? By comparison, in $\mathbb{R}^2$, it is easy to show that the boundaries of a Voronoi tesselation are hyperbolic arcs.</p> http://mathoverflow.net/questions/123025/the-right-conformal-map-to-make-a-certain-picture The right conformal map to make a certain picture John Gunnar Carlsson 2013-02-26T19:54:25Z 2013-02-26T22:03:35Z <p>This is a follow-up to a question I asked a year ago, which was helpfully answered by Anton Petrunin:</p> <p><a href="http://mathoverflow.net/questions/85624/fitting-a-mesh-to-a-density-function" rel="nofollow">http://mathoverflow.net/questions/85624/fitting-a-mesh-to-a-density-function</a></p> <p>I am trying to come up with a way to make a picture of an equilateral triangular mesh in the plane in which the density of triangles has elliptical level sets. For example, the following picture has a triangular mesh in which the density of triangles has <i>circular</i> level sets, which I obtained by taking the complex map $z\mapsto z^{2}$:</p> <p><img src="http://menet.umn.edu/~jgc/circular.png" alt="alt text"></p> <p>The picture below is closer to what I was looking for, but it's actually a total hack: I just took the complex map $z\mapsto \sin{z}$ and then physically <i>drew</i> a black ellipse in the center of the picture to suggest some kind of elliptical density:</p> <p><img src="http://menet.umn.edu/~jgc/elliptical.png" alt="PICTURE"></p> <p>If we zoom closer we can see that the level sets of the density are clearly not ellipses:</p> <p><img src="http://menet.umn.edu/~jgc/elliptical-zoomed.png" alt="alt text"></p> <p>Does anyone have suggestions for better maps that might produce the kind of picture I'm looking for? I browsed through the "Dictionary of Conformal Mappings" at <a href="http://math.fullerton.edu/mathews/c2003/ConformalMapDictionary.1.html" rel="nofollow">http://math.fullerton.edu/mathews/c2003/ConformalMapDictionary.1.html</a> but haven't been able to find anything better than what I've got.</p> http://mathoverflow.net/questions/116592/complexity-of-a-matching-problem-on-the-grid-mathbb-z2/116720#116720 Answer by John Gunnar Carlsson for Complexity of a matching problem on the grid $\mathbb Z^2$ John Gunnar Carlsson 2012-12-18T16:21:49Z 2012-12-18T16:21:49Z <p>I believe the full details, along the lines of what domotorp posted, are provided in "Reconstructing sets of orthogonal line segments in the plane" by Rendl and Woeginger. From the abstract,</p> <p>"We show that reconstructing a set of $n$ orthogonal line segments in the plane from the set of their vertices can be done in $O(n log n)$ time, if the segments are allowed to cross. If the segments are not allowed to cross, the problem becomes NP-complete."</p> <p>The authors give a reduction to planar 3-SAT that uses points on an integer lattice, which I believe is the setting you're interested in.</p> http://mathoverflow.net/questions/109096/honeycomb-type-properties-of-the-delaunay-triangulation-and-voronoi-diagram Honeycomb-type properties of the Delaunay triangulation and Voronoi diagram John Gunnar Carlsson 2012-10-07T20:02:13Z 2012-10-07T20:02:13Z <p>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:</p> <p>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</p> <p>2) The sum of the edge lengths in a Delaunay triangulation of $P$, notated $DT(P)$,</p> <p>so that my problem can be written as</p> <p><code>$\mathrm{minimize}_P ~ D_{avg}(P) +\phi DT(P)$</code></p> <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?</p> <p>The honeycomb conjecture, <a href="http://en.wikipedia.org/wiki/Honeycomb_conjecture" rel="nofollow">http://en.wikipedia.org/wiki/Honeycomb_conjecture</a> , 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.</p> http://mathoverflow.net/questions/100638/equitable-division-of-a-contiguous-resource Equitable division of a contiguous resource John Gunnar Carlsson 2012-06-25T22:22:49Z 2012-07-18T19:22:00Z <p>I have come across the following result regarding equitable division of a resource, which is a simple and immediate consequence of linear programming complementarity (in the infinite-dimensional case). I strongly suspect that it is a special case of some other well-known principle, perhaps in a related field such as economics or even geography, but as of yet I have not found any helpful leads. Can anyone suggest any results from which the statement below is a consequence? Any other leads will also be appreciated.</p> <p>Let $R$ denote a contiguous resource (such as a piece of land) that is to be divided into $n$ pieces $R_1,\dots,R_n$ among $n$ agents (so agent $i$ gets piece $R_i$). Suppose that each agent has a continuous "utility density" function $u_i(x)>0$ defined on $R$ and that $R$ also has a continuous "population density" $f(x)>0$ defined on it. The total "utility" that agent $i$ receives is then $\iint_{R_i} f(x)u_i(x) dx$. One might consider the problem of choosing $R_1,\dots,R_n$ as "equitably" as possible, say by maximizing the minimum utility of the agents:</p> <p>$\text{maximize}_{R_1,\dots,R_n}\lbrace\min_i \iint_{R_i} f(x)u_i(x) dx\rbrace$ subject to</p> <p>$\bigcup_i R_i = R$ and $R_i \cap R_j = \emptyset \text{ for all }i\neq j$</p> <p>It is easy to verify that, at the optimal solution $R_1^*,\dots,R_n^*$, all of the agents' utilities are equal.</p> <p>Now, define $q_i^* := \iint_{R_i^*} f(x) dx$ (the population of the $i$th optimal piece), and consider the problem of choosing regions to maximize the <i>total</i> utilities of the agents, but under a logarithmic utility function, and imposing constraints on the populations in each piece:</p> <p>$\text{maximize}_{R_1,\dots,R_n}\lbrace\sum_i \iint_{R_i} f(x)\log(u_i(x)) dx\rbrace$ subject to</p> <p>$\iint_{R_i} f(x) dx = q_i^*$</p> <p>$\bigcup_i R_i = R$ and $R_i \cap R_j = \emptyset \text{ for all }i\neq j$</p> <p>It is not hard to show that the solution to this problem is the same as the solution to the original problem. I have uploaded a MATLAB script that demonstrates this principle using cvx at</p> <p><a href="http://menet.umn.edu/~jgc/mathoverflow.m" rel="nofollow">http://menet.umn.edu/~jgc/mathoverflow.m</a></p> <p>if anyone is interested.</p> http://mathoverflow.net/questions/97862/determining-if-a-given-probability-distribution-in-the-plane-is-a-mixture-of-othe Determining if a given probability distribution in the plane is a mixture of others John Gunnar Carlsson 2012-05-24T19:16:47Z 2012-05-24T19:16:47Z <p>Suppose that $f_0(\cdot)$ is a probability distribution in the plane with a known mean $\mu_{0}\in\mathbb{R}^2$ and a covariance matrix $\Sigma_0\in\mathbb{R}^{2\times2}$ that is bounded by a linear matrix inequality, $S_0 - \Sigma_0 \succeq 0$, for some given (symmetric, positive semi-definite) $S_0$. Suppose we are given $n$ additional points $\mu_i\in\mathbb{R}^2$ and $n$ additional (symmetric, positive semi-definite) matrices $S_i\in\mathbb{R}^{2\times2}$. Is it easy to determine if there exist $n$ distributions $f_i(\cdot)$ such that:</p> <p>1) $f_0(\cdot)$ can be expressed as a convex combination of the distributions $f_i(\cdot)$,</p> <p>2) $\mu_i$ is the mean of $f_i(\cdot)$ for all $i$, and </p> <p>3) $S_i - \Sigma_i \succeq 0$ for all $i$, where $\Sigma_i$ is the covariance matrix of $f_i(\cdot)$?</p> <p>Is the problem easier if $f_0(\cdot)$ is discrete?</p> http://mathoverflow.net/questions/75030/clique-sizes-in-a-unit-disk-graph Clique sizes in a unit disk graph John Gunnar Carlsson 2011-09-09T19:01:06Z 2012-05-04T14:03:25Z <p>This is a spiritual successor to a question that Peter Shor answered here:</p> <p><a href="http://mathoverflow.net/questions/57017/generalized-euclidean-tsp" rel="nofollow">http://mathoverflow.net/questions/57017/generalized-euclidean-tsp</a></p> <p>Are there any results known on the asymptotic behavior of clique sizes in a unit disk graph with uniformly sampled points? That is, suppose I sample $N$ points uniformly in a square (or disk, or whatever figure is easiest to deal with) of size $L \times L$, and I draw an edge between two points if the distance between them is less than $1$. As $N$ becomes large, is anything known about the distribution of clique sizes in this graph?</p> http://mathoverflow.net/questions/86584/applications-of-k-medians-with-moment-constraints Applications of k-medians with moment constraints John Gunnar Carlsson 2012-01-24T22:55:52Z 2012-01-24T22:55:52Z <p>Suppose I have a collection of points $p_1,\dots,p_N$ in the plane. In the <em>Euclidean $k$-medians</em> (or <em>$k$-means</em>) problems, our objective is to distribute a set of $k$ points $x_1,\dots,x_k$ in the plane so as to minimize the distances (or squares of distances) to the points $p_i$, i.e. to minimize the quantity $\sum_{i=1}^{N} \min_j \| x_j - p_i \|$ (I am not requiring that the $x_j$'s be a subset of the $p_i$'s; they can lie anywhere in the plane). Obviously this problem has many practical applications.</p> <p>My question is: let's suppose we impose some constraints on the first or second moments of $x_1,\dots,x_k$, i.e. require that $\frac{1}{k}\sum_j x_j = x_0$ for some fixed point $x_0$, or that $\frac{1}{k} \sum_j \|x_j - \bar{x}\|^2 \leq S^2$ for some given threshold $S^2$. Is there any conceivable practical scenario where this might arise?</p> <p>I am not asking for assistance in solving this problem -- I'm really just interested in any thoughts on contexts where it might occur.</p> http://mathoverflow.net/questions/85787/2-3-power-law-in-the-plane 2/3 power law in the plane John Gunnar Carlsson 2012-01-16T04:25:15Z 2012-01-16T22:05:44Z <p>I've recently come across a particular problem whose solution turns out to be a probability distribution given by $f(x) = \alpha \|x\|^{-2/3}$ in the unit disk in $\mathbb{R}^2$ and zero elsewhere (I alluded to this in a previous question</p> <p><a href="http://mathoverflow.net/questions/85624/fitting-a-mesh-to-a-density-function" rel="nofollow">http://mathoverflow.net/questions/85624/fitting-a-mesh-to-a-density-function</a></p> <p>which was very helpfully answered by Anton Petrunin). Does this distribution appear in any other contexts? I've seen a $2/3$ power law in reference to metabolic rates of animals:</p> <p><a href="http://www.ncbi.nlm.nih.gov/pubmed/19906667" rel="nofollow">http://www.ncbi.nlm.nih.gov/pubmed/19906667</a></p> <p>and in kinematics:</p> <p><a href="http://www.ncbi.nlm.nih.gov/pubmed/9844558" rel="nofollow">http://www.ncbi.nlm.nih.gov/pubmed/9844558</a></p> <p>but both of the preceding cases appear to be looking at rather one-dimensional quantities (and they're positive powers rather than negative in my case, not an important distinction); they have $f(t) = \alpha t^{2/3}$, where $t$ represents mass in the first case and angular velocity of the tip of a pen in the second. This seems different from the situation that I'm describing. To put it succinctly,</p> <p>"Are there natural quantities that are proportional to the distance to some point, raised to the $-2/3$ power?"</p> <p>(This may be more appropriate for another forum; if so, I welcome any suggestions)</p> 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/84857/equitable-allocation-of-individuals-to-positions/84913#84913 Answer by John Gunnar Carlsson for Equitable Allocation of Individuals to Positions John Gunnar Carlsson 2012-01-04T22:56:02Z 2012-01-04T22:56:02Z <p>This is not a complete answer but too long for a comment. You wrote,</p> <blockquote> <p>I originally thought this could be framed as a linear programming problem, where the goal is to find weights for each of the n! possible orderings. Maybe this would work, but it would be computationally infeasible.</p> </blockquote> <p>Linear programs with this many variables are solved all the time using column generation:</p> <p><a href="http://www.columbia.edu/~cs2035/courses/ieor4600.S07/columngeneration.pdf" rel="nofollow">http://www.columbia.edu/~cs2035/courses/ieor4600.S07/columngeneration.pdf</a></p> <p>In your problem, let variable $q_k$ denote the probability of using permutation $\pi_k$, and let variable $p_{ij}$ denote the marginal probability that agent $i$ is assigned to $j$, so you have a total of $n! + n^2$ variables. Let $\pi_k(i,j) = 1$ if agent $i$ is assigned to position $j$ in permutation $k$ and zero otherwise. We can relate the $p_{ij}$'s and $q_k$'s via $n^2$ constraints of the form</p> <p>$\sum_k q_k \pi_k(i,j) = p_{ij} \forall i,j$</p> <p>Now, assume as Kevin did that $\sum_i v_i = \sum_j b_j = 1$. Your equity criterion is just $\sum_j p_{ij} v_j = b_i \forall i$. We obviously must require that $q_k \geq 0$ for all $k$. Thus the feasible set of these permutations can be written as:</p> <p>$\sum_k q_k = 1$</p> <p>$p_{ij} = \sum_k q_k \pi_k (i,j) \forall i,j$</p> <p>$q_k \geq 0 \forall k$</p> <p>$\sum_j p_{ij} v_j = b_i \forall i$</p> <p>There are a total of $1 + n^2 + n$ equality constraints and $n!$ inequality constraints, and you have $n! + n^2$ variables. Any basic feasible solution of this set (i.e. a corner point) therefore must have $n! - (n+1)$ of the inequality constraints active, which means that the corner points have only $n+1$ nonzero $q_k$'s. Thus, if your problem is feasible at all for particular choices of $v$ and $b$, it's possible to find such a set of assignments using at most $n+1$ possible permutations.</p> <p>You may gain further insight by looking at the dual of this LP -- the primal problem above has $n^2 + n!$ variables, $1 + n^2 + n$ equality constraints, and $n!$ inequality constraints, so its dual will have $n^2 + n!$ constraints, but only $1 + n^2 + n$ variables. Those constraints should have a nice structure to them (something like, one constraint for each permutation, and that constraint sums over all nonzero $\pi_k(i,j)$'s or something), which would give you a polynomial-time separation oracle for solving the dual LP. There may likely be a way to recover a primal solution from the dual using complementary slackness.</p> http://mathoverflow.net/questions/84484/computational-complexity-of-integration-in-two-dimensions/84653#84653 Answer by John Gunnar Carlsson for Computational complexity of integration in two dimensions John Gunnar Carlsson 2011-12-31T20:20:43Z 2011-12-31T22:07:58Z <p>Since you mentioned triangulation, Quarteroni, Sacco, and Saleri's book gives the following formula in the section on multi-dimensional integration: if your domain of integration is a convex polygon $\Omega$ with a triangulation $\mathcal{T}_h$ consisting of $N_T$ triangles, where $h$ is the maximum edge length in $\mathcal{T}_h$, and your quadrature rule has degree of exactness equal to $n$ with all nonnegative weights, then there exists a positive constant $K_n$, independent of $h$, such that the error $E$ is bounded by</p> <p>$|E| \leq K_n h^{n+1} |\Omega| M_{n+1}$</p> <p>where $M_{n+1}$ is the maximum value of the modules of the derivatives of order $n+1$ and $|\Omega|$ is the area of $\Omega$. The composite midpoint formula and the composite trapezoidal formula have nonnegative weights and degree of exactness $n=1$ and so we have</p> <p>$|E| \leq K_1 h^2 |\Omega| M_2$</p> <p>for some constant $K_1$. It follows that, if your desired error is $\epsilon$, then the maximum length of any edge of your triangulation $h$ must be at most $\epsilon^{1/2}(|\Omega| M_2 K_1)^{-1/2}$, i.e. $O(\epsilon^{1/2}(|\Omega| M_2)^{-1/2})$. If you break $\Omega$ into $N_T$ triangles as I mentioned before, the edge length will be $O(\sqrt{|\Omega|/N_T})$, so you'll need to break $\Omega$ into $O(\frac{|\Omega|^2 M_2}{\epsilon})$ triangles. So, quadratic in the area, linear in the maximum value of the second derivative, and inversely proportional to $\epsilon$. It's not clear to me where convexity enters the picture, so perhaps this will adapt to the general case you've described. The authors state that a proof can be found in Isaacson E. and Keller H. (1966), Analysis of Numerical Methods. Wiley, New York. (This is not my area of expertise so I welcome any corrections)</p> <p>UPDATE: I checked the Isaacson book and the relevant section, "7.4 Composite Formulae for Multiple Integrals" doesn't make any mention of convexity, so you may be safe in using the $O(\frac{|\Omega|^2 M_2}{\epsilon})$ that I gave before.</p> http://mathoverflow.net/questions/66684/area-preserving-map-between-rectangles-and-fat-polygons Area-preserving map between rectangles and fat polygons John Gunnar Carlsson 2011-06-01T19:53:13Z 2011-06-02T07:26:57Z <p>Are there any well-known continuous area-preserving maps between fat convex polygons and fat rectangles? Specifically, given a fat convex polygon $C$, is there a natural way to choose a fat rectangle $R$ and a continuous mapping $f:C\rightarrow R$ such that area of sub-regions is preserved? I've avoided giving a precise definition of "fatness", but two common definitions are:</p> <p>*The aspect ratio of the minimum bounding box of $C$ is bounded by some constant (see page 5 of <a href="http://portal.acm.org/citation.cfm?id=1137901" rel="nofollow">http://portal.acm.org/citation.cfm?id=1137901</a>).</p> <p>*The ratio between the diameters of the smallest circle containing $C$ and the largest circle contained in $C$ is bounded by some constant (see <a href="http://books.google.com/books?id=QS6vnl8WlnQC&amp;pg=PA588" rel="nofollow">http://books.google.com/books?id=QS6vnl8WlnQC&amp;pg=PA588</a>).</p> http://mathoverflow.net/questions/57017/generalized-euclidean-tsp Generalized Euclidean TSP John Gunnar Carlsson 2011-03-01T17:26:32Z 2011-03-01T22:57:52Z <p>Suppose I have n sets $X_1,\dots,X_n$ consisting of $k$ points each, where all $nk$ points are i.i.d. uniform random samples in the unit square $[0,1]\times[0,1]$. Consider the shortest path that goes through at least one element of each set $X_i$. Is the asymptotic behavior of this, a la the Beardwood-Halton-Hammersley (BHH) theorem, well-known? (By "asymptotic behavior", I mean, assume that $k$ is fixed and look at what happens as $n$ becomes large)</p> http://mathoverflow.net/questions/53296/average-distance-to-a-curve-of-fixed-length Average distance to a curve of fixed length John Gunnar Carlsson 2011-01-25T23:45:07Z 2011-01-26T00:08:18Z <p>Let $C$ be a continuous curve in the unit square having length $L$. Is there a lower bound on the <em>average distance</em> between the points in the unit square and $C$, as a function of $L$? Is there an asymptotic behavior that's known as $L$ gets large? (other suggestions for tags are welcome)</p> http://mathoverflow.net/questions/49989/algorithm-for-k-medians-in-a-convex-polygon/50381#50381 Answer by John Gunnar Carlsson for Algorithm for k-medians in a convex polygon John Gunnar Carlsson 2010-12-25T23:15:58Z 2010-12-25T23:15:58Z <p>A while ago I wrote, but never published, an approximation algorithm for this problem. Using some new results and updating the citations, it looks like I can get the approximation constant down to 9.026 (assuming I didn't make any mistakes). It's not clear to me if that's publication-worthy, but I uploaded a draft to</p> <p><a href="http://www.tc.umn.edu/~jcarlsso/fermat-weber.pdf" rel="nofollow">http://www.tc.umn.edu/~jcarlsso/fermat-weber.pdf</a></p> <p>if anyone is interested.</p> http://mathoverflow.net/questions/120634/robust-optimization-in-matlab-using-fmincon Comment by John Gunnar Carlsson John Gunnar Carlsson 2013-02-03T03:30:50Z 2013-02-03T03:30:50Z Your constraint doesn't make sense as stated. Are you trying to say something like $$\min_{\chi\in[0,1]} |\alpha||\omega|[\cos\phi - \chi]=r_p$$ for some given $r_p$? Is $\Sigma$ positive semidefinite? Who are &quot;the authors&quot;? If this is a convex problem, you're probably much better off using cvx rather than fmincon. http://mathoverflow.net/questions/100638/equitable-division-of-a-contiguous-resource Comment by John Gunnar Carlsson John Gunnar Carlsson 2012-06-26T00:28:56Z 2012-06-26T00:28:56Z @Joseph O'Rourke: Hi Joseph! Yes, actually, one can prove that when $u_i(x) = \|x-p_i\|$ for a point $p_i$, the optimal solution to both is a multiplicatively weighted Voronoi diagram; I proved this (for the first of the two problems I gave in this post) in the paper &quot;Dividing a territory among several facilities&quot; on my website. http://mathoverflow.net/questions/85787/2-3-power-law-in-the-plane/85853#85853 Comment by John Gunnar Carlsson John Gunnar Carlsson 2012-01-17T18:22:39Z 2012-01-17T18:22:39Z Good one, thanks! http://mathoverflow.net/questions/85624/fitting-a-mesh-to-a-density-function/85688#85688 Comment by John Gunnar Carlsson John Gunnar Carlsson 2012-01-15T20:32:48Z 2012-01-15T20:32:48Z Got it! Many thanks! http://mathoverflow.net/questions/85624/fitting-a-mesh-to-a-density-function/85688#85688 Comment by John Gunnar Carlsson John Gunnar Carlsson 2012-01-15T09:05:35Z 2012-01-15T09:05:35Z Ah, interesting; many thanks for the follow-up. When you say &quot;$f=\alpha{\cdot}|x|^{-\beta}$ is OK once the domain is simply connected&quot;, 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) http://mathoverflow.net/questions/85624/fitting-a-mesh-to-a-density-function/85688#85688 Comment by John Gunnar Carlsson John Gunnar Carlsson 2012-01-15T02:40:38Z 2012-01-15T02:40:38Z 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? http://mathoverflow.net/questions/75030/clique-sizes-in-a-unit-disk-graph/82744#82744 Comment by John Gunnar Carlsson John Gunnar Carlsson 2012-01-01T21:05:23Z 2012-01-01T21:05:23Z Thanks, Tobias! http://mathoverflow.net/questions/84610/strength-of-hypothesis-tests Comment by John Gunnar Carlsson John Gunnar Carlsson 2011-12-30T21:38:12Z 2011-12-30T21:38:12Z Thanks, I'll cross-post there. Should I kill this thread? http://mathoverflow.net/questions/70189/proving-that-a-functions-image-contains-1-n-1-n/70278#70278 Comment by John Gunnar Carlsson John Gunnar Carlsson 2011-07-14T02:06:54Z 2011-07-14T02:06:54Z Oh yes, my mistake. Deleted the incorrect answer; sorry for that. http://mathoverflow.net/questions/66684/area-preserving-map-between-rectangles-and-fat-polygons/66689#66689 Comment by John Gunnar Carlsson John Gunnar Carlsson 2011-06-01T21:07:50Z 2011-06-01T21:07:50Z Thanks! Just what I was looking for. http://mathoverflow.net/questions/66684/area-preserving-map-between-rectangles-and-fat-polygons/66688#66688 Comment by John Gunnar Carlsson John Gunnar Carlsson 2011-06-01T21:07:37Z 2011-06-01T21:07:37Z Thanks! I wasn't aware of that book. http://mathoverflow.net/questions/66684/area-preserving-map-between-rectangles-and-fat-polygons Comment by John Gunnar Carlsson John Gunnar Carlsson 2011-06-01T20:33:22Z 2011-06-01T20:33:22Z Thanks. Continuity is required and I edited the question to reflect that. Piecewise linearity would be nice but not necessary. http://mathoverflow.net/questions/66684/area-preserving-map-between-rectangles-and-fat-polygons Comment by John Gunnar Carlsson John Gunnar Carlsson 2011-06-01T20:03:23Z 2011-06-01T20:03:23Z Good point, put in two examples. http://mathoverflow.net/questions/57017/generalized-euclidean-tsp Comment by John Gunnar Carlsson John Gunnar Carlsson 2011-03-01T18:53:19Z 2011-03-01T18:53:19Z I'm assuming that $k$ is fixed, and we're looking at the behavior as $n$ goes to infinity. http://mathoverflow.net/questions/57017/generalized-euclidean-tsp Comment by John Gunnar Carlsson John Gunnar Carlsson 2011-03-01T17:58:40Z 2011-03-01T17:58:40Z Beardwood-Halton-Hammersley. It says that, when $k=1$ in my problem (i.e. the shortest path through $n$ uniformly sampled points), the path length scales with $\sqrt{n}$: <a href="http://myweb.lsbu.ac.uk/~whittyr/MathSci/TheoremOfTheDay/OR/BHH/TotDBHH.pdf" rel="nofollow">myweb.lsbu.ac.uk/~whittyr/MathSci/TheoremOfTheDay/&hellip;</a>