User john gunnar carlsson - MathOverflow

Boundary surfaces in a 3d Voronoi tessellation with obstacles

2013-05-08T18:07:49Z

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.

The right conformal map to make a certain picture

2013-02-26T19:54:25Z

This is a follow-up to a question I asked a year ago, which was helpfully answered by Anton Petrunin:

http://mathoverflow.net/questions/85624/fitting-a-mesh-to-a-density-function

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 circular level sets, which I obtained by taking the complex map $z\mapsto z^{2}$:

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 drew a black ellipse in the center of the picture to suggest some kind of elliptical density:

If we zoom closer we can see that the level sets of the density are clearly not ellipses:

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 http://math.fullerton.edu/mathews/c2003/ConformalMapDictionary.1.html but haven't been able to find anything better than what I've got.

Answer by John Gunnar Carlsson for Complexity of a matching problem on the grid $\mathbb Z^2$

2012-12-18T16:21:49Z

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,

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

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.

Honeycomb-type properties of the Delaunay triangulation and Voronoi diagram

2012-10-07T20:02:13Z

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, http://en.wikipedia.org/wiki/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.

Equitable division of a contiguous resource

2012-06-25T22:22:49Z

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.

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:

$\text{maximize}_{R_1,\dots,R_n}\lbrace\min_i \iint_{R_i} f(x)u_i(x) dx\rbrace$ subject to

$\bigcup_i R_i = R$ and $R_i \cap R_j = \emptyset \text{ for all }i\neq j$

It is easy to verify that, at the optimal solution $R_1^*,\dots,R_n^*$, all of the agents' utilities are equal.

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 total utilities of the agents, but under a logarithmic utility function, and imposing constraints on the populations in each piece:

$\text{maximize}_{R_1,\dots,R_n}\lbrace\sum_i \iint_{R_i} f(x)\log(u_i(x)) dx\rbrace$ subject to

$\iint_{R_i} f(x) dx = q_i^*$

$\bigcup_i R_i = R$ and $R_i \cap R_j = \emptyset \text{ for all }i\neq j$

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

http://menet.umn.edu/~jgc/mathoverflow.m

if anyone is interested.

Determining if a given probability distribution in the plane is a mixture of others

2012-05-24T19:16:47Z

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:

1) $f_0(\cdot)$ can be expressed as a convex combination of the distributions $f_i(\cdot)$,

2) $\mu_i$ is the mean of $f_i(\cdot)$ for all $i$, and

3) $S_i - \Sigma_i \succeq 0$ for all $i$, where $\Sigma_i$ is the covariance matrix of $f_i(\cdot)$?

Is the problem easier if $f_0(\cdot)$ is discrete?

Clique sizes in a unit disk graph

2011-09-09T19:01:06Z

This is a spiritual successor to a question that Peter Shor answered here:

http://mathoverflow.net/questions/57017/generalized-euclidean-tsp

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?

Applications of k-medians with moment constraints

2012-01-24T22:55:52Z

Suppose I have a collection of points $p_1,\dots,p_N$ in the plane. In the Euclidean $k$-medians (or $k$-means) 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.

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?

I am not asking for assistance in solving this problem -- I'm really just interested in any thoughts on contexts where it might occur.

2/3 power law in the plane

2012-01-16T04:25:15Z

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

http://mathoverflow.net/questions/85624/fitting-a-mesh-to-a-density-function

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:

http://www.ncbi.nlm.nih.gov/pubmed/19906667

and in kinematics:

http://www.ncbi.nlm.nih.gov/pubmed/9844558

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,

"Are there natural quantities that are proportional to the distance to some point, raised to the $-2/3$ power?"

(This may be more appropriate for another forum; if so, I welcome any suggestions)

Fitting a mesh to a density function

2012-01-14T00:16:44Z

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.

Answer by John Gunnar Carlsson for Equitable Allocation of Individuals to Positions

2012-01-04T22:56:02Z

This is not a complete answer but too long for a comment. You wrote,

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.

Linear programs with this many variables are solved all the time using column generation:

http://www.columbia.edu/~cs2035/courses/ieor4600.S07/columngeneration.pdf

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

$\sum_k q_k \pi_k(i,j) = p_{ij} \forall i,j$

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:

$\sum_k q_k = 1$

$p_{ij} = \sum_k q_k \pi_k (i,j) \forall i,j$

$q_k \geq 0 \forall k$

$\sum_j p_{ij} v_j = b_i \forall i$

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.

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.

Answer by John Gunnar Carlsson for Computational complexity of integration in two dimensions

2011-12-31T20:20:43Z

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

$|E| \leq K_n h^{n+1} |\Omega| M_{n+1}$

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

$|E| \leq K_1 h^2 |\Omega| M_2$

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)

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.

Area-preserving map between rectangles and fat polygons

2011-06-01T19:53:13Z

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:

*The aspect ratio of the minimum bounding box of $C$ is bounded by some constant (see page 5 of http://portal.acm.org/citation.cfm?id=1137901).

*The ratio between the diameters of the smallest circle containing $C$ and the largest circle contained in $C$ is bounded by some constant (see http://books.google.com/books?id=QS6vnl8WlnQC&pg=PA588).

Generalized Euclidean TSP

2011-03-01T17:26:32Z

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)

Average distance to a curve of fixed length

2011-01-25T23:45:07Z

Let $C$ be a continuous curve in the unit square having length $L$. Is there a lower bound on the average distance 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)

Answer by John Gunnar Carlsson for Algorithm for k-medians in a convex polygon

2010-12-25T23:15:58Z

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

http://www.tc.umn.edu/~jcarlsso/fermat-weber.pdf

if anyone is interested.

Comment by John Gunnar Carlsson

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 "the authors"? If this is a convex problem, you're probably much better off using cvx rather than fmincon.

Comment by John Gunnar Carlsson

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 "Dividing a territory among several facilities" on my website.

Comment by John Gunnar Carlsson

2012-01-17T18:22:39Z

Good one, thanks!

Comment by John Gunnar Carlsson

2012-01-15T20:32:48Z

Got it! Many thanks!

Comment by John Gunnar Carlsson

2012-01-15T09:05:35Z

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)

Comment by John Gunnar Carlsson

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?

Comment by John Gunnar Carlsson

2012-01-01T21:05:23Z

Thanks, Tobias!

Comment by John Gunnar Carlsson

2011-12-30T21:38:12Z

Thanks, I'll cross-post there. Should I kill this thread?

Comment by John Gunnar Carlsson

2011-07-14T02:06:54Z

Oh yes, my mistake. Deleted the incorrect answer; sorry for that.

Comment by John Gunnar Carlsson

2011-06-01T21:07:50Z

Thanks! Just what I was looking for.

Comment by John Gunnar Carlsson

2011-06-01T21:07:37Z

Thanks! I wasn't aware of that book.

Comment by John Gunnar Carlsson

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.

Comment by John Gunnar Carlsson

2011-06-01T20:03:23Z

Good point, put in two examples.

Comment by John Gunnar Carlsson

2011-03-01T18:53:19Z

I'm assuming that $k$ is fixed, and we're looking at the behavior as $n$ goes to infinity.

Comment by John Gunnar Carlsson

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}$: myweb.lsbu.ac.uk/~whittyr/MathSci/TheoremOfTheDay/…